Diameter of Binary Tree

easyTrees: Traversal52 stepsJava · Python · C++

The diameter is the longest path (in edges) between any two nodes. The longest path through a node is height(left) + height(right). Compute heights bottom-up and keep the best sum seen.

▶ Watch the animated trace

Traced input: root = [1, 2, 3, 4, 5] → 3. Original problem: neetcode.io/problems/binary-tree-diameter

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(h)

One post-order traversal.

Key idea

Every path has a highest node; at that node it's left height + right height.
The recursion returns height; the diameter is tracked on the side.
The path doesn't have to pass through the root.

Common mistakes

Assuming the diameter goes through the root.
Counting nodes instead of edges.

Solution

Java

int best;

int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    depth(root);
    return best;
}

int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left);
    int right = depth(node.right);
    best = Math.max(best, left + right);
    return 1 + Math.max(left, right);
}

Python

def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
    best = 0

    def depth(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node: return 0
        left = depth(node.left)
        right = depth(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)

    depth(root)
    return best

C++

int best;

int depth(TreeNode* node) {
    if (!node) return 0;
    int left = depth(node->left);
    int right = depth(node->right);
    best = max(best, left + right);
    return 1 + max(left, right);
}

int diameterOfBinaryTree(TreeNode* root) {
    best = 0;
    depth(root);
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single node No edges.	`root = [1]`	`0`
Two nodes One edge.	`root = [1, 2]`	`1`
Longest path avoids the root 5-3-2-4-6 bends at node 2, below the root.	`root = [1, 2, null, 3, 4, 5, null, null, 6]`	`4`