Tree: Height of a Binary Tree

This problem was asked in Hacker Rank.

Tree

  1. Preorder Traversal
  2. Inorder Traversal
  3. Postorder Traversal

Problem

Given a function which has a parameter: a pointer to the root of a binary tree. It must return the height of the tree.

Write a function:

function getHeight(node);

that, given a pointer of root node and must return the height of the tree.

Note -The Height of binary tree with single node is taken as zero.

Examples

  1. Sample input:
     2
      \
       2
        \
         5
        /  \
       3    6
        \
         4

Output:

4
  1. Sample input:
      1
    /   \
   2     3
  / \   / \
 4   5 6   7

Output:

3

Write an efficient algorithm for the following assumptions

  • 1 <= Nodes in the tree <= 500

Solution

Javascript Solution

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

let height = 0;

function getHeight(rootNode, level) {
  if (!rootNode) {
    return;
  }
  if (height < level) {
    height = level;
  }

  getHeight(rootNode.left, level + 1);
  getHeight(rootNode.right, level + 1);
}

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

getHeight(root, 0);
console.log("Height ", height);

Java Solution

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
  static int height = 0;
	public static int height(Node root) {
      	// Write your code here.
          Solution.heightView(root, 0);

          return Solution.height;
    }

    public static void heightView(Node root, int level){
        if(root == null){
            return;
        }

        if(Solution.height < level){
            Solution.height = level;
        }
        Solution.heightView(root.left, level + 1);
        Solution.heightView(root.right, level + 1);

    }
}

Result

I have passed all the test cases.

Preorder Traversal

💌 If you’d like to receive more coding solutions in your inbox, you can sign up for the newsletter here.

Discussions

Up next