Objective: Given a binary tree, find the height of it
Input: A Binary Tree
Output: Height of a binary tree
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)
Complete Code:
| public class TreeHeight { | |
| public int treeHeight(Node root){ | |
| if(root==null)return 0; | |
| return (1+ Math.max(treeHeight(root.left),treeHeight(root.right))); | |
| } | |
| public static void main (String[] args) throws java.lang.Exception | |
| { | |
| Node root = new Node(5); | |
| root.left = new Node(10); | |
| root.right = new Node(15); | |
| root.left.left = new Node(20); | |
| root.left.right = new Node(25); | |
| root.left.left.left =new Node(30); | |
| root.left.right.left = new Node(35); | |
| root.left.right.left.left = new Node(40); | |
| root.left.right.left.left.right = new Node(45); | |
| root.left.right.left.left.right.left = new Node(50); | |
| TreeHeight i = new TreeHeight(); | |
| System.out.println("Tree Height: "+i.treeHeight(root)); | |
| } | |
| } | |
| class Node{ | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data){ | |
| this.data = data; | |
| this.left = null; | |
| this.right = null; | |
| } | |
| } |
Output:
Height of the Tree is 7
Explanation with diagram is just amazing! Thanks!
Thanks Anuj
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.
public int treeHeight(Node root){
if(root==null)return -1;
return (1+ Math.max(treeHeight(root.left),treeHeight(root.right)));
}
This would work