The height of a binary tree is found using the recursive [Depth-First Search](https://www.educative.io/answers/what-is-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.

#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;
}

public class main{
  private class Node{
    Node left;
    Node right;
  }

  Node root;

  main(){
    root = new Node();
  
    // Creating 2nd level (or generation):
    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;
  }

  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;
  }

  public static void main(String[] args){
    main m = new main();
    System.out.println("Height of tree: " + m.findHeight(m.root));
  }
}

Java

class Node:
  def __init__(self):
    self.left = None;
    self.right = None;

class BST:
  def __init__(self):
    self.root = Node();

    # Creating 2nd level:
    one = Node();
    two = Node();
    self.root.left = one;
    self.root.right = Node();

    # Creating 3rd level:
    three = Node();
    four = Node();
    five = Node();
    one.left = three;
    two.left = four;
    two.right = five;

  def findMax(self, a, b):
    if a >= b:
      return a;
    else:
      return b;
  
  def findHeight(self, root):
    # Base case:
    if root is None:
      return 0;

    return self.findMax(self.findHeight(root.left), self.findHeight(root.right)) + 1;

myTree = BST();

print("Height of tree: ", myTree.findHeight(myTree.root))







Python

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:   Base case: If there is no node, return 0.   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.   

How to find the height of a binary tree

Implementation