Height of binary tree

One of the most basic problems on binary search tree is to find height of binary search tree or binary tree. First of all, what do we mean by height of binary search tree or height of binary tree? Height of tree is the maximum distance between the root node and any leaf node of the tree. For example, height of tree given below is 5, distance between node(10) and node(8). Note that we have multiple lea nodes, however we chose the node which s farthest from the root node.

height of binary tree

Height of binary tree : Thoughts

Brute force method to find height will be to calculate distance of each node from the root and take the maximum of it. As we will traversing each node of tree complexity will be O(n) and we need O(2logn) space to store distance for each leaf node.

What if we go bottom up instead of measuring distance of leaf nodes from root? What will be height of leaf node? At leaf node, there is no tree below it, hence height should be 1, which is node itself. What will be height of empty tree where root itself is null? It will be zero.
What if a node has a left subtree? Then height of subtree at that node will be height of left subtree + 1 (for the node itself). Same is true if node has only right subtree.

Interesting case is when node has both left and right subtree. Which height we should take to get height of subtree at node? As we are looking for maximum distance, we should take maximum of both subtrees and add 1 to get height at that node.

As we are going bottom up and building the height up from leaf to node, it is necessary to pass on height of left subtree and right subtree to root node. It means we have to process subtrees before root node. What kind of traversal is it? As in Delete binary search tree and Mirror binary search tree this problem is also postorder traversal of binary tree with specific processing at root node.

Let’s take and example and see how this method works? Given below binary tree,find height of it.

height of binary tree

We have to start from bottom and for that follow the path till node is current node is null. At root node(10), is it node null? No, then move down the left subtree.

Is node(5) null? Nope, again move down to left subtree.

At node(4), it is not null, hence we move down to left subtree. But as left child of node(4) is null, it we will return 0 as height of an empty binary tree should be 0. Again, node(4) does not even have right child, so from right side too it gets a zero. What will be height of node(40) then? Max(0,0 ) + 1 = 1, which it returns back to parent node(5).

Back at node(5), we go the height of left subtree, there is right subtree too, so we will find height of it, before judging the height of subtree at node(5). So move down the right side of node(5).

Node(7) is not null, so move down the left subtree of it, which is node(6).

Node(6) is also not null, hence we move down the left subtree which is null. Null subtree returns 0. It is same for right subtree of node(6). So, node(6) return max(0,0) + 1 = 1 to parent node.

Back at node(7), there is right subtree too, so move down it to node(9).

As node(9) is not null, move down the left child which is node(8).

We move left of node(8) which is null and even right subtree is null, as all leaf node, it also return 1 to parent node.

 

At node(9), right child is null which return 0. So what should be height of node(9)? It will be max(1,0) + 1 = 2. 1 is height of left subtree and 0 is height of right subtree.
In the same vein, node(7) will return 3 to node(5).

At node(5), return max(1,3) +1 = 4.

 

Now, at node(10), we have height of left subtree let’s calculate height of right subtree. Move down to node(14).

 

Node(14) not null, move to left subtree to node(12).

 

As node(12) is not null, move to left side, which being null, return 0. Similarly for right child, it also returns 0. So, node(12) return max(0,0) +1 to parent node.

Move down to right subtree of node(14) to node(15).

As explained other cases, node(15) too will return 1.

At this point, we have height of left subtree and right subtree of node(14), hence return height  = max(1,1) + 1 = 2 to parent node.

Here, at node(10), we have height of left and right subtrees. What will be height of the binary tree then? it will be max(4,2) + 1 = 5.

Hope this example clarifies how recursive bottom up approach works to find height of binary tree.

Height of binary tree : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node Node;

#define MAX(a,b)  (a < b ? b : a)

Node *createNode(int value){
    Node * newNode =  (Node *)malloc(sizeof(Node));
	
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;
	
    return newNode;
}

Node *addNode(Node *node, int value){
    if(!node) return createNode(value);
        
    if (node->value > value)
        node->left = addNode(node->left, value);
    else
        node->right = addNode(node->right, value);
		
    return node;
}

int height( Node *root){
    if( !root ) return 0;
    
    int lheight = height( root->left);
    int rheight = height( root->right);
	
    return 1 + MAX (lheight, rheight );
}

/* Driver program for the function written above */
int main(){
    Node *root = NULL;
	
    //Creating a binary tree
    root = addNode(root, 30);
    root = addNode(root, 20);
    root = addNode(root, 15);
    root = addNode(root, 25);
    root = addNode(root, 40);
    root = addNode(root, 38);
    root = addNode(root, 39);
    root = addNode(root, 45);
    
    printf( "Height of tree is : %d", height( root));
    
    return 0;
}

Complexity of recursive method is O(n) as we will b scanning all nodes at least once. Be aware of drawback of recursive nature of this implementation as it may lead of stack overflow in production environments.

Two important things we learn from this problem : First how to traverse a tree which is part of solution to many of binary tree problems. Second, how to return values for subtrees to root and process those values at root node. We saw same thing happening in Replace node with sum of children in BST.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us at communications@algorithmsandme.com