Given a binary tree, find height of it. Height of empty tree is -1, height of tree with one node is 0 and height of below tree is 3.

##### Example 1: Print height/depth of a Binary Tree

Input:

**Output: **Height: 3

## Solutions

### Method 1: Recursion

Height of a tree is the **max [height of left-sub-tree, height of right-sub-tree] + 1**, we can solve this problem with Recursion easily.

Calculate height of left and right sub-trees and return max (left, right)+1, the base condition would be - "-1" height for a null tree.

##### Complexity

The time complexity of this solution is

**O(n)**and space complexity is**O(n)**due to recursive calls.