Height of Tree in Data Structure
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 nary tree with the help of the number of nodes $(V)$ is:
If there are V nodes in an nary tree (a node can have at most n children), the maximum height of the tree is $(V1)$ 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 onebyone 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++
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 levelorder 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++
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 realworld 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 nary tree (a node can have at most n children), the maximum height of the tree is $(V1)$, and the minimum height is $ceil(lognV)$.
 The height of a tree can be calculated using recursive and iterative methods.