Height of a binary tree

Abhishek Kumar • Category: Data Structures • Tags: datastructures tree binary-tree

Height of a tree is the total number of nodes on the path from the root node to the deepest node in the tree.
Find the height of a binary tree using the recursive and iterative solution.

Height of a tree

It is the total number of nodes on the path from the root node to the deepest node in the tree. A tree with only a root node has a height of 1.
(Sometimes tree with one root node only considered as height 0 but here are following convention of height 1 if the tree has only one node.)

Similary, we can calculate the height if any node in the tree i.e., total number of nodes on the path from that node to the deepest node in the tree.

To find the height of a binary tree we have to traverse to the deepest node and then count the number of nodes in the path from root to that deepest node.

We can solve this problem in two ways-

Recursive solution
Iterative solution

Recursive solution

For recursive solution we have to check height of each child one by one recursively as we have done in binary tree recursive traversal. Other types of traversal can also be used.

Python
Javascript

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

def height(root):
    if root is None:
        return 0
    return max(height(root.left), height(root.right)) + 1

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(height(root))

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function height(root) {
  if (!root) return 0;

  lHeight = height(root.left);
  rHeight = height(root.right);

  if (lHeight >= rHeight) return lHeight + 1;
  else return rHeight + 1;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
console.log(height(root));

Output

Iterative solution

For iterative solution, we will be following slightly similar approach as level order traversal and calculate the height.

Python
Javascript

import queue

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

def height(root):
    if root is None:
        return 0
    
    height = 0
    q = queue.Queue()
    q.put(root)

    while(True):
        node_count = q.qsize()
        if node_count == 0 :
            return height
      
        height += 1
        while node_count > 0:
            node = q.get()
            if node.left:
                q.put(node.left)
            if node.right:
                q.put(node.right)
            node_count -= 1

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(height(root))

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function height(root) {
  if (!root) return 0;

  let height = 0;
  const q = [];
  q.push(root);

  while (true) {
    nodeCount = q.length;
    if (nodeCount == 0) return height;

    height++;
    while (nodeCount > 0) {
      const node = q.shift();
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
      nodeCount--;
    }
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
console.log(height(root));

Output

Size of a binary tree

Deepest node in a binary tree

AUTHOR

Abhishek Kumar

Height of a binary tree

Height of a tree

Recursive solution

Output

Iterative solution

Output

Abhishek Kumar

Recommended Posts -