How to count the height of a binary tree

Given a binary tree, return binary tree height

Note : The height of the binary tree is the number of edges in the longest path from the root node to a leaf node.

 

Example

 

Output: 2

 

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/
public sealed class Solution
{
    public int Height(TreeNode root)
    {
    }
}

Approach:

Almost all binary tree problems can be solved using recursion or without it. Let's use recursion for this one.

The height of a binary tree can be represented as: 1 + maximum between height of the left subtree and height of the right subtree.

 

 

Code

    public int Height(TreeNode root)
    {
        if (root == null)
        {
            return -1;
        }

        int leftHeight = Height(root.Left);
        int rightHeight = Height(root.Right);

        return Math.Max(leftHeight, rightHeight) + 1;
    }

Time Complexity: O(n)