Lets Code Them Up!

Diameter of the Binary Tree

Given a binary tree, you need to compute the length of the diameter of the 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 the path between two nodes is represented by the number of edges between them.

Solution

It’s clear that we need to find the length of the longest path between two nodes in a tree. So here those nodes are either 4 and 3 or 5 and 3. Both 5 and 5 are the leaf nodes of the right subtree and 3 is the leaf node of the left subtree. The depth of the tree is the max length from root to leaf. It could be safely said, the max diameter will be the max depth of left subtree and right subtree at any time. For a node root of the tree, we need to do following –

  1. Find the depth of left child
  2. Find the depth of right child
  3. Update global variable diameter with the sum of left and right depth if it is more than depth’s current value.
  4. return depth of the root

Both the time and space complexity will of O(n) where n is the number of nodes in the binary tree. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
/**
 * DiameterOfBinaryTree.java
 * Purpose: Find the diameter of Binary Tree
 *
 * @author Megha Rastogi
 * @version 1.0 08/03/2020
 */
class DiameterOfBinaryTree {
    // ans variable to track diameter
    int ans = 0;
    
    /**
     * Find the diameter of Binary Tree
     *
     * @param root, TreeNode
     * @return integer, diameter
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        depth(root);
        return ans-1;
    }
    
    /**
     * Helper method to find the diameter of a binary tree
     *
     * @param root, TreeNode
     * @return integer, diameter
     */
    public int depth(TreeNode root){
        // return 0 when reaching leaf nodes
        if(root == null)
            return 0;
        
        // left node depth
        int left = depth(root.left);
     
        // right node depth
        int right = depth(root.right);
     
        // update diameter with the max diameter till now
        ans = Math.max(ans, left+right+1);
     
        //return depth till this node
        return Math.max(left, right)+1;
    }
}

Source – leetcode

Code – DiameterOfBinaryTree.java

Megha

,
, , ,