Height of Tree in Data Structure

What is the Height of a Tree in Data Structure?

The height of a tree (also known as depth) is the maximum distance between the root node of the tree and the leaf node of the tree. It can also be defined as the number of edges from the root node to the leaf node. The root node is at level 0. Therefore, if there is only one node, i.e., the root node, the height of the tree is 0.

The formula to determine the height of a n-ary tree with the help of the number of nodes $(V)$ is:

How to Find the Height of a Tree in Data Structure?

As we know, the height of a tree is the longest or maximum distance between the leaf node and the root node. Therefore, we need to find the path between the root and all the leaf nodes and find the longest one of all.

Two Ways to Calculate the Height of a Tree

1. Recursive Way
2. Iterative Way

Let's talk about the Recursive and Iterative ways by one-by-one in detail.

Recursive Way

Recursion involves dividing a large problem into smaller subproblems and returning the answer to their calls. We will work similarly to find the height of the tree. We will calculate the results of the subproblems and then return their results to the parent problem.

Algorithm

1. In order to calculate the height of the tree, we have to find the height of the left and right subtree recursively and then add 1 to them, i.e., the height between the topmost node and its children.
2. The recursion will run until the subtrees are NULL or the height of the tree is 1.
3. And finally, we will compare the heights of the left and right subtrees and return to the larger one.

Code

C++

Java

Python

Complexity Analysis

• Time Complexity

  The above recursive solution has an $O(n)$ time complexity, where n is the total number of nodes in the binary tree.

• Space Complexity

  The program needs $O(h)$ of additional space for the call stack, where h is the tree's height.

Iterative Way

In the iterative method, we find the height of the tree using the queue data structure. In this, we traverse the whole tree in a level-order traversal format where we maintain the nodes of each tree level in a queue data structure until all the levels are traversed and return the count of the number of levels.

Algorithm

1. Insert the root of a tree into a queue.
2. Traverse the tree in level order, inserting the child elements of all currently present nodes in the queue and removing those nodes.
3. Increment Count for each level in the queue.
4. Return the value of the counter when the queue becomes empty, i.e., when all the levels of the tree are traversed.

Code

C++

Java

Python

Complexity Analysis

• Time Complexity

  The time complexity of the above iterative solution is $O(n)$, where n is the total number of nodes in the binary tree.

• Space Complexity

  The auxiliary space required by the program is $O(n)$ for the queue data structure.

Ready to transform your coding skills? Our Java DSA course will equip you with the tools to solve real-world programming challenges.