The height of a Binary Tree is defined as the maximum depth of any leaf node from the root node. That is, it is the length of the longest path from the root node to any leaf node.
Let us consider the below Binary Tree.
Since the leaf nodes corresponding to the maximum depth are 40 and 50, to find the height, we simply find the number of edges from the root node to either one of these two nodes, which is 3.
Now that we know what the height of a Binary tree signifies, we shall now construct an algorithm to find the height of any Binary Tree.
Let us now decide the logic behind finding the height and write our pseudo code first.
We shall use recursion on the tree, to find the height. (Refer to the Wikipedia article for the concepts)
Since the height of the tree is defined as the largest path from the root to a leaf, we can recursively compute the height of the left and right sub-trees.
We can apply the definition of the height on the sub-trees now.
We observe that it is the maximum between the left and the right sub-trees and then add one.
Since the height of the tree is the maximum height of the sub-tree + 1, we keep doing this, until the sub-tree becomes NULL
, and it’s height is 0.
At this point, our function will finally terminate, and
Let’s write the function tree_height()
that computes the height.
Line #3 evaluates the terminating condition, when the sub-tree size is 0, or when the root node is NULL
.
Lines 7 and 8 recursively find the height of the left and right sub-trees.
And finally, Line 11 returns the maximum among the two, returning the height of the tree.
The below is a complete program showing how the Binary Tree is constructed, and then shows the logic for finding the height in tree_height()
.
Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.
in your example based on what you said “Since the leaf nodes corresponding to the maximum depth are 40 and 50, to find the height, we simply find the number of edges from the root node to either one of these two nodes, which is 3.” height of the tree is 2, not 3, right? because there are two edges from the root to 40 or 50. Can you please confirm?
- Mohsen Vafa