@dsadaily

  • Home
  • Tags
  • About
  • TryMe

Diameter of a Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

Problem Statement

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

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

Approach

The longest path between two nodes in a binary tree will always be between two leaf nodes as otherwise we can always increase the length of the path by moving to next child node.

To solve this problem, our algorithm will identify the node where the combined length of its longest left and right branches is the greatest. This value represents the diameter of the binary tree.

Implementation

Following is a java based recursive approach to solve this problem:

private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
    calc(root);
    return diameter;
}
private int calc(TreeNode root){
    if(null == root){
        return 0;
    }
    int left = calc(root.left);
    int right = calc(root.right);
    
    diameter = Math.max(diameter, left + right);

    // return height of the current node
    return Math.max(left, right) + 1;
}

The diameter of the binary tree is the sum of the heights of the left and right subtrees of the current node. This does not include the current node itself as the diameter is represented by the number of edges between two nodes.

Complexity Analysis

The time complexity for this approach is O(n) where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

The space complexity is O(n) as we are using recursion and the maximum depth of the recursion tree can be n in case of a skewed binary tree. If the binary tree is balanced, the space complexity will be O(log n).

Be notified of new posts. Subscribe to the RSS feed.