Find height of binary tree in java using BFS/level order traversal (example)

• Given a binary tree, find out the height of binary using non recursive algorithm.
• Traverse the binary tree using level order traversal or breadth first search algorithm.
• What is height of Binary tree?
  • The longest path from root to deepest leaf node, defines the height of a binary tree.
• Root node of a binary tree is assumed to be at Height 1.
  • Calculate the height of binary tree wrt. root node.

Example: find height of a binary tree in java using non recursive algorithm.

• Root Node 60 is at  Height 1
• Nodes 20, 80 are at Height  2
• Nodes 10,30,70,90 are at Height 3
• Nodes 65,75,85,95 are at Height 4

Longest path from Root to deepest node is at Height 4.

Algorithm: calculate height of binary tree using breadth first search

• Root is at height 1.
  • Push root node to queue.
• Add null to the queue
  • null will be level delimiter (marker that we have finished the current level)
• Start iterating through the Queue till it is empty
• Pop node from queue
• Check node is null (if yes, we are next level)
  • Increment height by 1 & add level delimiter (null)
• Add next level children (left or/and right)
• At end of iteration, we will get the height of tree

Time complexity of algorithm is O(n).

Program: find height of binary tree in java using non recursive algorithm

1.) HeightOfTree Class:

• HeightOfTree class is responsible for finding the height of a binary tree.
• We will traverse the binary tree using level order traversal or non recursive algorithm.

package org.learn.Question;

import java.util.LinkedList;
import java.util.Queue;

public class HeightOfTree {
 public static int heightOfTree(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return -1;
  }
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);
  // level delimiter
  queue.offer(null);
  int height = 0;
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   if (null == node) {
    if (!queue.isEmpty()) {
     // level delimiter
     queue.offer(null);
    }
    height++;
   } else {
    if (node.left != null) {
     queue.offer(node.left);
    }
    if (node.right != null) {
     queue.offer(node.right);
    }
   }
  }
  return height;
 }
}

2.) Node Class:

• Node class is representing the node(s) of  a binary tree.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }

 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

•  We are constructing the binary in main method.
• We are calling method of HeightOfTree class to find height of binary tree using BFS or level order traversal algorithm.

package org.learn.Client;

import org.learn.Question.HeightOfTree;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(60);
  // Level 1
  Node B = Node.createNode(20);
  Node C = Node.createNode(80);
  // Level 2
  Node D = Node.createNode(10);
  Node E = Node.createNode(30);
  Node F = Node.createNode(70);
  Node G = Node.createNode(90);
  // Level 3
  Node H = Node.createNode(65);
  Node I = Node.createNode(75);
  Node J = Node.createNode(85);
  Node K = Node.createNode(95);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;
  // connect level 2 and level 3
  F.left = H;
  F.right = I;
  G.left = J;
  G.right = K;

  int height = HeightOfTree.heightOfTree(null);
  if (height > 0) {
   System.out.println("Height of a Binary Tree : " + height);
  } else {
   System.out.println("Unable to calculate height of a binary tree");
  }

 }
}

Output: Height of binary tree using breadth first search algorithm

Height of Binary Tree : 4

Download Code – Height Of Binary Tree (Non Recursive)