Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

height
binary
tree

How to find the height of a binary tree

Educative Answers Team

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

RELATED TAGS

height
binary
tree
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring