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

**Recursive Way****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**

- 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. - The
**recursion**will run until the subtrees are NULL or the height of the tree is 1. - And finally, we will compare the heights of the left and right subtrees and return to the larger one.

**Code**

**C++**

*// Recursive function to calculate the height of a given tree*
int height(Node *root){
*// Base case: Empty tree has a height equals 0*
if (root == nullptr){
return 0;
}
*// Calling Left and Right node recursively*
return 1 + max(height(root->left), height(root->right));
}

**Java**

*// Recursive function to calculate the height of a given tree*
public static int height(Node root){
*// Base case: Empty tree has a height equals 0*
if (root == null) {
return 0;
}
*// Calling Left and Right node recursively*
return 1 + Math.max(height(root.left), height(root.right));
}

**Python**

*# Recursive function to calculate the height of a given tree*
def height(root):
*# Base case: Empty tree has a height equals 0*
if root is None:
return 0
*# Calling Left and Right node recursively*
return 1 + max(height(root.left), height(root.right))

**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**

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

**Code**

**C++**

```
int height(Node *root){
```*// Empty tree has a height equals 0*
if (root == nullptr){
return 0;
}
*// Create an empty queue and insert the root node*
list<Node *> queue;
queue.push_back(root);
Node *front = nullptr;
int height = 0;
*// Run a loop until queue is empty*
while (!queue.empty()){
*// Calculate the total number of nodes at the current level*
int size = queue.size();
while (size--){
front = queue.front();
queue.pop_front();
if (front->left){
queue.push_back(front->left);
}
if (front->right){
queue.push_back(front->right);
}
}
*// Increment height by 1 for each level*
height++;
}
return height;
}

**Java**

```
public static int height(Node root){
```*// Empty tree has a height equals 0*
if (root == null) {
return 0;
}
*// Create an empty queue and insert the root node*
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
Node front = null;
int height = 0;
*// Run a loop until queue is empty*
while (!queue.isEmpty()){
*// Calculate the total number of nodes at the current level*
int size = queue.size();
while (size-- > 0){
front = queue.poll();
if (front.left != null) {
queue.add(front.left);
}
if (front.right != null) {
queue.add(front.right);
}
}
*// Increment height by 1 for each level*
height++;
}
return height;
}

**Python**

```
def height(root):
```*# Empty tree has a height equals 0*
if root is None:
return 0
*# Create an empty queue and insert the root node*
queue = deque() *# import deque*
queue.append(root)
height = 0
*# Run a loop until queue is empty*
while queue:
*# Calculate the total number of nodes at the current level*
size = len(queue)
while size > 0:
front = queue.popleft()
if front.left:
queue.append(front.left)
if front.right:
queue.append(front.right)
size = size - 1
*# Increment height by 1 for each level*
height = height + 1
return height

**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)*ceil*(*lognV*). - The height of a tree can be calculated using
**recursive**and**iterative methods**.