Diameter of a Binary Tree

Time: O(n)

Space: O(h)

Intuition

Diameter passes through some node (LCA). For each node, diameter through it = leftHeight + rightHeight. Track global maximum.

Algorithm

1DFS returning height of subtree.
2At each node: diameter candidate = leftHeight + rightHeight.
3Update global max. Return 1 + max(leftHeight, rightHeight) as height.

Example Walkthrough

Input: root=[1,2,3,4,5]

1.Node 4: h=1. Node 5: h=1. Node 2: dia=2, h=2. Node 3: h=1. Node 1: dia=1+2=3, h=3.

Output: 3

Common Pitfalls

•Diameter doesn't have to pass through root. Update global max at every node.

Diameter of a Binary Tree.java

Java

// Approach: DFS. For each node, diameter through it = height(left) + height(right). Track global max.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    int ans = 0;

    int diameter(Node root) {
        depth(root);
        return ans;
    }

    int depth(Node root) {
        if (root == null)
            return 0;

        int left = depth(root.left);
        int right = depth(root.right);

        ans = Math.max(ans, left + right);

        return (1 + Math.max(left, right));
    }
}

Was this solution helpful?