How to find the Height and Diameter of the Binary Tree

Hi friends, in this article, we going to see about how to find the height and diameter of Binary Tree.

Height of Binary Tree

Before finding the diameter of Binary Tree, we must have basic knowledge of how to find the Height of binary tree.

Look at the below problem to find the Height(Maximum Depth) of binary tree.

Given a binary tree, find its Height

The height is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

Solution – Easy to Understand

public class TreeNode {
      public int val;
      public TreeNode left;
      public TreeNode right;
      public TreeNode(int x) 
      {
          val = x; 
      }
}
class BinaryTree {
  
    static int FindHeightOfTree(TreeNode root)
    {
        //Base Case
        if(root == null)
            return 0;
        
        int leftSubtreeHeight = FindHeightOfTree(root.left);
        int rightSubtreeHeight = FindHeightOfTree(root.right);
        
        int totalHeight = 1 + Math.Max(leftSubtreeHeight,rightSubtreeHeight);
        return totalHeight;
    }
    static TreeNode CreateNewNode(int val)
    {
        TreeNode newNode = new TreeNode(val);
        newNode.left = null;
        newNode.right = null;
        return newNode;
    }
    static void Main() {
        TreeNode root = CreateNewNode(1);
        root.left =  CreateNewNode(2);
        root.right = CreateNewNode(3);
        root.left.left = CreateNewNode(4);
        root.left.right = CreateNewNode(5);
        int heightOfTree = FindHeightOfTree(root);
        Console.WriteLine("Height of Tree is " +heightOfTree);
        
    }
}

This above program, helps us to find the Height of Binary Tree.

Diameter of Binary Tree

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

    static int DiameterOfBinaryTree(TreeNode root)
    {
        if(root == null)
            return 0;
        
        /* Get the height of left and right sub trees */
        int leftSubTreeHeight = FindHeightOfTree(root.left);
        int rightSubTreeHeight = FindHeightOfTree(root.right);
        
        /* Get the diameter of left and right subtrees */
        int lDiameter = DiameterOfBinaryTree(root.left);
        int rDiameter = DiameterOfBinaryTree(root.right);
        
  /* Return max of following three 
          1) Diameter of left subtree 
         2) Diameter of right subtree 
         3) Height of left subtree + height of right subtree + 1 */

    return Math.Max(leftSubTreeHeight + rightSubTreeHeight + 1,Math.Max(lDiameter,rDiameter));
    }

Time Complexity: O(n * h)

Because every time, whenever we visit node, it calculates height, so it leads to O(n * h).

In our next post, we going to see about finding the Diameter of Binary Tree with improved O(n) time complexity.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s