How to find the height of a binary tree

The height of a binary tree is found using the recursive Depth-First Search (DFS) algorithm, as shown below:

  1. Base case: If there is no node, return 0.

  2. Else: If there are 1 or 2 children, return the maximum of the height of the left and right sub-trees, plus 1 to account for the current node. The height of a sub-tree is found by recursively calling the function, and passing the child node as the parameter.

1 of 16

Implementation

#include <iostream>
using namespace std;
struct Node{
Node* left;
Node* right;
};
Node* createTree(){
Node* root = new Node();
// Creating 2nd level:
Node* one = new Node();
Node* two = new Node();
root->left = one;
root->right = two;
// Creating 3rd level:
Node* three = new Node();
Node* four = new Node();
Node* five = new Node();
one->left = three;
two->left = four;
two->right = five;
return root;
}
int findMax(int a, int b){
if(a >= b)
return a;
else
return b;
}
int findHeight(Node* root){
// Base case:
if(root == NULL)
return 0;
return findMax(findHeight(root->left), findHeight(root->right)) + 1;
}
int main() {
Node* root = createTree();
cout << "Height of tree: " << findHeight(root);
return 0;
}
Finding height of a BST
Copyright ©2024 Educative, Inc. All rights reserved