**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