What is the brute force approach and complexity for Diameter of Binary Tree?

At each node, measure the left and right chains with fresh searches, then add them with time complexity O(N²) and space complexity O(H).

What is the optimal approach and complexity for Diameter of Binary Tree?

One post-order pass: each node returns its height and records the path that bends at it with optimal time complexity O(N) and space complexity O(H).

How do you identify the pattern for Diameter of Binary Tree?

Look for key signals in the prompt: "longest path between any two nodes" indicates The path can bend at any node, so every node must be checked, not just the root.; "may or may not pass through the root" indicates This is not a root-to-leaf question. The answer depends on the best bend point.; "number of edges" indicates Count the edges between nodes. A single node has diameter 0..

Diameter of Binary Tree

Easy·LeetCode #543Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree DFS: subtree answers (bottom-up)

Complexity:O(N²)→O(N)

Key Insight

Each node returns the number of nodes on its longest chain going down. While it combines its two children's answers, it also checks the path that bends at this node: left chain + right chain. The largest value seen anywhere is the answer. Every node is visited once.

Core Validity Invariant

Every path has one highest node, and its length is the deepest left chain plus the deepest right chain of that node, counted in edges.

Problem

You are given the root of a binary tree. Find its diameter: the number of edges on the longest path between any two nodes.

The path does not have to pass through the root. It can go up from one node and down into another part of the tree, or it can stay on one side of the root.

Input

The root of a binary tree. It has between 1 and 10^4 nodes.

Output

One number: the number of edges on the longest path.

Example 1

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

Output: 3

The longest path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3). It has 3 edges and passes through the root.

Example 2

Input: root = [1, 2]

Output: 1

There is only one edge, so the longest path is 1 → 2.

Example 3

Input: root = [1, 2, null, 4, 5, 6, null, null, 7]

Output: 4

The longest path is 6 → 4 → 2 → 5 → 7. It has 4 edges and does not touch the root.

Constraints

• The number of nodes is in the range [1, 10^4].
• −100 ≤ Node.val ≤ 100

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A path can start and end at any two nodes. Does it always have to pass through the root?
2.
Every path has a highest node, where it turns around. If I pick one node, what two pieces of the tree does a path through it join?
3.
How long is the longest straight chain going down from one child? Can I get that for each child first?
4.
The question asks for edges. How many edges does a path with one node have?
5.
If the left and right children each report their chain length, can this node work out its own best path without looking at the tree again?

Brute force approach

Idea

Every path has a top node where it bends. For each node, measure the longest chain down its left side and the longest chain down its right side, each with a fresh height() call. Add them. The largest sum over all nodes is the diameter.

Thinking process

1
The best path bends at some node. Its length is the left chain plus the right chain.
2
So try every node as the bend. On [1, 2, null, 4, 5, 6, null, null, 7], node 2 has left chain 2 → 4 → 6 (2 edges) and right chain 2 → 5 → 7 (2 edges). Total 4.
3
height() walks the whole subtree below its start, and it is called again for every node. The same nodes are walked over and over.
4
Keep the largest sum seen in best. At the end, best is the answer.

Visual

Blue = the node being checked. Green = walked for the first time in this check. Orange = walked again, because an earlier check already walked it.

Brute force walks the same nodes againroot = [1, 2, null, 3, null, 4, null, 5]step 1/6

tree

Work

node being checked: 1
walks this step: 4
already walked before: 0
total visits so far: 4
best: 4

height() walks 4 nodes; 0 were walked before

Node 1: left height 4 and right height 0 are measured from scratch. Orange nodes were already walked in an earlier step.

Code & Implementation

brute.cpp

class Solution {
    // Nodes on the longest downward chain from `node` (an empty tree has 0).
    // Every call walks the whole subtree again, from scratch.
    int height(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }

    // Treat every node as the place where the path bends.
    void checkEveryNode(TreeNode* node, int& best) {
        if (!node) return;
        int lh = height(node->left);    // separate search for the left side
        int rh = height(node->right);   // separate search for the right side
        best = max(best, lh + rh);      // edges: left chain + right chain
        checkEveryNode(node->left, best);
        checkEveryNode(node->right, best);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        int best = 0;
        checkEveryNode(root, best);
        return best;
    }
};

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 {
    // Nodes on the longest downward chain from `node` (an empty tree has 0).
    // Every call walks the whole subtree again, from scratch.
    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    private int best = 0;

    // Treat every node as the place where the path bends.
    private void checkEveryNode(TreeNode node) {
        if (node == null) return;
        int lh = height(node.left);  // separate search for the left side
        int rh = height(node.right); // separate search for the right side
        best = Math.max(best, lh + rh); // edges: left chain + right chain
        checkEveryNode(node.left);
        checkEveryNode(node.right);
    }

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

from typing import Optional, List, Dict, Tuple

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # Nodes on the longest downward chain from `node` (an empty tree has 0).
    # Every call walks the whole subtree again, from scratch.
    def height(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        return 1 + max(self.height(node.left), self.height(node.right))

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

        # Treat every node as the place where the path bends.
        def checkEveryNode(node: Optional[TreeNode]) -> None:
            nonlocal best
            if not node:
                return
            lh = self.height(node.left)   # separate search for the left side
            rh = self.height(node.right)  # separate search for the right side
            best = max(best, lh + rh)     # edges: left chain + right chain
            checkEveryNode(node.left)
            checkEveryNode(node.right)

        checkEveryNode(root)
        return best

export 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);
    }
}

// Nodes on the longest downward chain from `node` (an empty tree has 0).
// Every call walks the whole subtree again, from scratch.
function height(node: TreeNode | null): number {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

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

    // Treat every node as the place where the path bends.
    function checkEveryNode(node: TreeNode | null): void {
        if (!node) return;
        const lh = height(node.left);  // separate search for the left side
        const rh = height(node.right); // separate search for the right side
        best = Math.max(best, lh + rh); // edges: left chain + right chain
        checkEveryNode(node.left);
        checkEveryNode(node.right);
    }

    checkEveryNode(root);
    return best;
}

Complexity

Time O(N²)Space O(H)

On a chain of N nodes, the call at the top walks N − 1 nodes, the next one walks N − 2, and so on. That is about N²/2 steps. The optimal version walks every node once and gets both sides' heights from the same recursion.

Optimized approach

Idea

Start from brute force

The brute force calls height() once for each child of each node. Every call walks a whole subtree again, and those subtrees overlap.

Find the repeated work

A node's height is needed by its parent's path check and by every ancestor's check. The brute force walks the subtree again each time, but the answer is already known once the children are finished.

Define the state — what variables do I need?

height (return value): Number of nodes on the longest chain going down from this node. An empty tree gives 0.
lh, rh: The heights returned by the left and right children. Each one is also the number of edges from this node down to the deepest node on that side.
best: Longest path found so far, in edges. It starts at 0, because a single node has no edges.

Define validity

Every path has one highest node, and its length is the deepest left chain plus the deepest right chain of that node, counted in edges.

Define the transitions — when does each pointer move, and why is it safe?

Before the recursion

best = 0

A single node is a path with 0 edges, so 0 is the smallest possible answer.

After both children return

best = max(best, lh + rh)

lh is the number of nodes on the left chain, which is also the number of edges from this node down to its deepest left node. The same holds for rh. So lh + rh is the length of the path that bends here, in edges.

Before returning to the parent

return 1 + max(lh, rh)

The parent can only extend one side of this node. It needs the height of the longer chain plus this node.

What does the current window add to the answer?

Each node adds one candidate: the path that bends at it. Every path has a highest node, so the largest candidate over all nodes is the diameter.

Code & Implementation

optimal.cpp

class Solution {
    // Returns the number of nodes on the longest downward chain from `node`.
    // While combining the two children, it also records the path that bends at `node`.
    int height(TreeNode* node, int& best) {
        if (!node) return 0;
        int lh = height(node->left, best);
        int rh = height(node->right, best);
        // lh (or rh) is also the number of edges from node down to its deepest leaf on that side.
        best = max(best, lh + rh);
        return 1 + max(lh, rh);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        int best = 0;
        height(root, best);
        return best;
    }
};

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 {
    private int best = 0;

    // Returns the number of nodes on the longest downward chain from `node`.
    // While combining the two children, it also records the path that bends at `node`.
    private int height(TreeNode node) {
        if (node == null) return 0;
        int lh = height(node.left);
        int rh = height(node.right);
        // lh (or rh) is also the number of edges from node down to its deepest leaf on that side.
        best = Math.max(best, lh + rh);
        return 1 + Math.max(lh, rh);
    }

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

from typing import Optional, List, Dict, Tuple

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # Returns the number of nodes on the longest downward chain from `node`.
    # While combining the two children, it also records the path that bends at `node`.
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0

        def height(node: Optional[TreeNode]) -> int:
            nonlocal best
            if not node:
                return 0
            lh = height(node.left)
            rh = height(node.right)
            # lh (or rh) is also the number of edges from node down to its deepest leaf on that side.
            best = max(best, lh + rh)
            return 1 + max(lh, rh)

        height(root)
        return best

export 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);
    }
}

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

    // Returns the number of nodes on the longest downward chain from `node`.
    // While combining the two children, it also records the path that bends at `node`.
    function height(node: TreeNode | null): number {
        if (!node) return 0;
        const lh = height(node.left);
        const rh = height(node.right);
        // lh (or rh) is also the number of edges from node down to its deepest leaf on that side.
        best = Math.max(best, lh + rh);
        return 1 + Math.max(lh, rh);
    }

    height(root);
    return best;
}

Complexity

Time O(N)Space O(H)

Each child returns exactly once, so every node is visited once. The recursion stack is H deep: O(log N) for a balanced tree, O(N) for a chain.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	At each node, measure the left and right chains with fresh searches, then add them	O(N²)	O(H)
Optimal	One post-order pass: each node returns its height and records the path that bends at it	O(N)	O(H)

Why does this belong to this pattern?

Clues in the problem statement

“longest path between any two nodes”The path can bend at any node, so every node must be checked, not just the root.
“may or may not pass through the root”This is not a root-to-leaf question. The answer depends on the best bend point.
“number of edges”Count the edges between nodes. A single node has diameter 0.

Each node returns its height to its parent+best = max over all nodes of (left height + right height)+count edges, not nodes→Tree DFS: subtree answers (bottom-up)

Each node returns one number to its parent: its height. The answer is different: it can bend at any node, so it is kept in best and updated while combining. This is the pattern in one sentence: return one summary upward, and record the whole-tree answer on the way. The next question, Balanced Binary Tree, uses the same post-order shape but returns a yes/no flag.

Don't make this mistake

Pattern confusion: the answer does not have to bend at the root

✗ int lh = height(root->left), rh = height(root->right); return lh + rh;

✓ // check lh + rh at every node and keep the largest in best

On [1, 2, null, 4, 5, 6, null, null, 7] the root has one side of height 3 and an empty right side, so this returns 3. The real answer is 4: the path 6 → 4 → 2 → 5 → 7 bends at node 2 and never touches the root. Diameter is a maximum over all nodes.

Counting nodes instead of edges

✗ best = max(best, lh + rh + 1);

✓ best = max(best, lh + rh);

The question counts edges. On [1, 2, 3] the path 2 → 1 → 3 has 2 edges, but the wrong line gives 3. On the single node [1] it gives 1 instead of 0. lh and rh already count the edges from this node down each side, so do not add 1.

Returning the whole path upward

✗ return 1 + lh + rh;

✓ return 1 + max(lh, rh);

A parent can extend only one side of a node. On [1, 2, 3, 4, 5, 6, null, null, 7], node 2 would return 5 instead of 3. The root would then add its other side and report 6 edges. No path in this 7-node tree has 6 edges. Both sides count only at the bend, never on the way up.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture