# Height of Tree in Data Structure

Video Tutorial
FREE
This video belongs to
Java DSA Course - Master the Fundamentals and Beyond
12 modules
Certificate
Topics Covered

## Overview

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

The most common type of tree is the binary tree. In this, each node has 2 children, i.e., Left and Right.

The node that doesn’t have any parents is known as the root node, and the node that doesn't have any children nodes is known as the leaf node. There is one root node in a tree, but there can be numerous leaf nodes.

## Takeaways

The maximum height of a tree in the data structure is the maximum distance between the root and the last leaf node.

## 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:

If there are V nodes in an n-ary tree (a node can have at most n children), the maximum height of the tree is $(V-1)$ and the minimum height is $ceil(lognV)$.

## 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.

## Conclusion

Let's summarize the article by what we have discussed so far.

• A tree is a hierarchical data structure with parent and child nodes.
• There is a single root node and a number of leaf nodes.
• If there are V nodes in an n-ary tree (a node can have at most n children), the maximum height of the tree is $(V-1)$, and the minimum height is $ceil(lognV)$.
• The height of a tree can be calculated using recursive and iterative methods.