Diameter of Binary Tree

EASY

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 path between two nodes is represented by the number of edges between them.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    int max_diameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        calculateMaximumDiameter(root);
        return max_diameter;
    }
    
    private int calculateMaximumDiameter(TreeNode node){
        if(node == null){
            return 0;
        }
        int left_diameter = calculateMaximumDiameter(node.left);
        int right_diameter = calculateMaximumDiameter(node.right);
        int current_diameter = (left_diameter + right_diameter);
        max_diameter = Math.max(max_diameter, current_diameter);
        return Math.max(left_diameter, right_diameter) + 1;
    }
}

The recursion tree will look like as following

                1 (3)
             /        \
          2[2]        3[1]
        /    \        /   \   
      4[1]   5[1]    [0]  [0] 
     /  \    /  \   
   [0]  [0] [0]  [0]

Complexity Analysis

  • Time Complexity: O(N). We visit every node once.
  • Space Complexity: O(N), the size of our implicit call stack during our depth-first search.

Categories: Binary Tree

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