Solution For Diameter Of Binary Tree

Problem:

Given the root of a binary tree, return 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.

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

Solution:

The diameter of a binary tree is defined as the maximum of the following three values:

The diameter of the left subtree from the root node.
The diameter of the right subtree from the root node.
The longest path between any two nodes that goes through the root node.

Therefore, the solution involves recursively computing the height of left and right subtrees of every node and taking the maximum of the sum of their heights plus 1.

Firstly, we check for an empty tree, if the root is None return 0.

Secondly, recursively calculate the max depth of left and right child of the root node.

Then, compute the maximum diameter of all maximum depths. Here, the maximum diameter is the maximum of the following three values:

• The diameter of the left subtree from the root node.
• The diameter of the right subtree from the root node.
• The longest path between any two nodes that goes through the root node (which is the sum of the maximum depths of left and right subtree plus 1).

Code:

Here is the python implementation for the solution of Diameter of Binary Tree problem:

“`
class Solution(object):
def diameterOfBinaryTree(self, root):
“””
:type root: TreeNode
:rtype: int
“””
# Base case
if not root:
return 0

    # Compute the maximum depth of left and right subtree recursively
    l_depth = self.maxDepth(root.left)
    r_depth = self.maxDepth(root.right)

    # Compute the maximum diameter of all maximum depths
    max_diameter = max(l_depth + r_depth, 
                       self.diameterOfBinaryTree(root.left), 
                       self.diameterOfBinaryTree(root.right))
    return max_diameter

def maxDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    # Base case
    if not root:
        return 0

    # Compute the maximum depth of left and right subtree recursively
    l_depth = self.maxDepth(root.left)
    r_depth = self.maxDepth(root.right)

    # Return the one with greater sum plus 1
    return max(l_depth, r_depth) + 1

“`

The time complexity of the above solution is O(n^2), where n is the number of nodes in the binary tree. This is because we are computing the maximum depth of left and right subtrees of every node, which takes O(n) time.

However, we can optimize the solution by computing the maximum depth and diameter of the binary tree in a single traversal. This can be done by keeping track of the maximum diameter of all nodes while computing the maximum depth. The optimized solution has a time complexity of O(n).

Step by Step Implementation For Diameter Of Binary Tree

/**
 * 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 = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        max = Math.max(max, left + right);
        
        return Math.max(left, right) + 1;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        # get the height of left and right subtrees
        left_height = self.get_height(root.left)
        right_height = self.get_height(root.right)
        
        # get the diameter of left and right subtrees
        left_diameter = self.diameterOfBinaryTree(root.left)
        right_diameter = self.diameterOfBinaryTree(root.right)
        
        # return the max of the three
        return max(left_height + right_height, left_diameter, right_diameter)
    
    def get_height(self, root):
        if not root:
            return 0
        return 1 + max(self.get_height(root.left), self.get_height(root.right))

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    // base case
    if (!root) return 0;
    
    // diameter is the longest path between any two nodes in the tree
    // the longest path goes through the root
    // so we need to find the longest path from the root to any node in the tree
    
    // get the height of the left and right subtrees
    let leftHeight = getHeight(root.left);
    let rightHeight = getHeight(root.right);
    
    // get the longest path through the left and right subtrees
    let leftDiameter = diameterOfBinaryTree(root.left);
    let rightDiameter = diameterOfBinaryTree(root.right);
    
    // return the longest path
    return Math.max(leftHeight + rightHeight, Math.max(leftDiameter, rightDiameter));
};

function getHeight(root) {
    // base case
    if (!root) return 0;
    
    // get the height of the left and right subtrees
    let leftHeight = getHeight(root.left);
    let rightHeight = getHeight(root.right);
    
    // return the tallest subtree
    return 1 + Math.max(leftHeight, rightHeight);
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int lheight = height(root->left);
        int rheight = height(root->right);
        
        int ldiameter = diameterOfBinaryTree(root->left);
        int rdiameter = diameterOfBinaryTree(root->right);
        
        return max(lheight + rheight, max(ldiameter, rdiameter));
    }
    
    int height(TreeNode* node) {
        if(!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int DiameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        int left = DiameterOfBinaryTree(root.left);
        int right = DiameterOfBinaryTree(root.right);
        return Math.Max(left, right) + 1;
    }
}