Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

Find the Maximum Depth OR Height of a Binary Tree

Objective: Given a binary tree, find the height of it

Input: A Binary Tree

Output: Height of a binary tree

Example:

Tree Height - Example

Tree Height – Example

Approach:

       Recursion:

  • Get the height of left sub tree, say leftHeight
  • Get the height of right sub tree, say rightHeight
  • Take the Max(leftHeight, rightHeight) and add 1 for the root and return
  • Call recursively.

Time Complexity : O(n)

get Height of a tree - Recursion

get Height of a tree – Recursion

Complete Code:


Output:

Height of the Tree is 7

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • Anuj

    Explanation with diagram is just amazing! Thanks!

    • tutorialhorizon

      Thanks Anuj

  • Ardalan Yousefi

    The height of a single-node tree is zero by definition, not one. You should check if your root has any children before adding 1 to the height.

    • Rui Tang (Nathan)

      public int treeHeight(Node root){
      if(root==null)return -1;
      return (1+ Math.max(treeHeight(root.left),treeHeight(root.right)));
      }

      This would work

%d bloggers like this: