Diameter of Binary Tree easy

Problem Statement

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.

Example 1

Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2

Input: root = [1,2] Output: 1

Steps

  1. Recursive Depth-First Search (DFS): We'll use a recursive DFS approach to traverse the tree. For each node, we need to find the maximum depth of its left and right subtrees.

  2. Diameter Calculation: The diameter at any node is the sum of the depths of its left and right subtrees. We'll keep track of the global maximum diameter found so far.

  3. Return Value: The recursive function will return the maximum depth of the subtree rooted at the current node. The global variable will hold the final diameter.

Explanation

The key insight is that the diameter might not pass through the root. Therefore, we need to explore all possible paths. Our DFS approach elegantly handles this by calculating the maximum depth of the left and right subtrees at each node, and using this information to update the overall diameter. The function dfs recursively computes the maximum depth of a subtree while simultaneously updating the maxDiameter.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function diameterOfBinaryTree(root: TreeNode | null): number {
    let maxDiameter = 0;

    function dfs(node: TreeNode | null): number {
        if (!node) {
            return 0;
        }

        let leftDepth = dfs(node.left);
        let rightDepth = dfs(node.right);

        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    dfs(root);
    return maxDiameter;
};

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the DFS traversal.

  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is logâ‚‚N.