543. Diameter of Binary Tree (Easy)

Problem

Given the root of a binary tree, return the length of the diameter, the longest path between any two nodes in the tree. The path may or may not pass through the root. Length is measured in edges.

Example

• root = [1,2,3,4,5] → 3 (path: 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3)

LeetCode 543 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, for each node, compute left + right heights

At every node, compute the height of its left and right subtrees, and track the max of (left + right).

Python

def diameter_of_binary_tree(root):
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))  # L1: O(n) subtree walk

    best = 0
    def visit(node):
        nonlocal best
        if not node:
            return
        best = max(best, height(node.left) + height(node.right))  # L2: O(n) per node
        visit(node.left)                                           # L3: recurse
        visit(node.right)

    visit(root)
    return best

TypeScript

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

function diameterOfBinaryTree(root: TreeNode | null): number {
    function height(node: TreeNode | null): number {
        if (!node) return 0;
        return 1 + Math.max(height(node.left), height(node.right));  // L1: O(n) subtree walk
    }
    let best = 0;
    function visit(node: TreeNode | null): void {
        if (!node) return;
        best = Math.max(best, height(node.left) + height(node.right));  // L2: O(n) per node
        visit(node.left);                                                // L3: recurse
        visit(node.right);
    }
    visit(root);
    return best;
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func treeHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }
    l := treeHeight(node.Left)
    r := treeHeight(node.Right)
    if l > r {
        return 1 + l                              // L1: O(n) subtree walk
    }
    return 1 + r
}

func diameterOfBinaryTree(root *TreeNode) int {
    best := 0
    var visit func(*TreeNode)
    visit = func(node *TreeNode) {
        if node == nil {
            return
        }
        l := treeHeight(node.Left)
        r := treeHeight(node.Right)
        if l+r > best {
            best = l + r                          // L2: O(n) per node
        }
        visit(node.Left)                          // L3: recurse
        visit(node.Right)
    }
    visit(root)
    return best
}

Swift

final class Solution { func diameterOfBinaryTree(_ root: TreeNode?) -> Int { guard let root else { return 0 }; return max(height(root.left) + height(root.right), max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right))) }; private func height(_ node: TreeNode?) -> Int { guard let node else { return 0 }; return 1 + max(height(node.left), height(node.right)) } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L2 (height calls)	$O(n)$	n nodes	$O(n²)$ ← dominates
L3 (recurse visit)	$O(1)$ dispatch	n	$O(n)$

height is called for every node via visit, and each call walks the full subtree. Redundant work accumulates quadratically.

Complexity

• Time: $O(n²)$. height is called for every node, each call is $O(n)$ worst case, driven by L2.
• Space: $O(h)$ recursion.

Approach 2: Single DFS that returns height and updates diameter (optimal)

Rewrite height so that while computing a node’s height, it also updates a running maximum diameter. Each node is visited once.

Python

def diameter_of_binary_tree(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)              # L1: recurse left
        right = height(node.right)            # L2: recurse right
        best = max(best, left + right)        # L3: O(1) update diameter
        return 1 + max(left, right)           # L4: O(1) return height to parent

    height(root)
    return best

TypeScript

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

    function height(node: TreeNode | null): number {
        if (!node) return 0;
        const left = height(node.left);              // L1: recurse left
        const right = height(node.right);            // L2: recurse right
        best = Math.max(best, left + right);         // L3: O(1) update diameter
        return 1 + Math.max(left, right);            // L4: O(1) return height to parent
    }

    height(root);
    return best;
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
    best := 0
    var heightFn func(*TreeNode) int
    heightFn = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := heightFn(node.Left)               // L1: recurse left
        right := heightFn(node.Right)             // L2: recurse right
        if left+right > best {
            best = left + right                   // L3: O(1) update diameter
        }
        if left > right {
            return 1 + left                       // L4: O(1) return height to parent
        }
        return 1 + right
    }
    heightFn(root)
    return best
}

Swift

final class Solution { func diameterOfBinaryTree(_ root: TreeNode?) -> Int { var diameter = 0; func height(_ node: TreeNode?) -> Int { guard let node else { return 0 }; let left = height(node.left), right = height(node.right); diameter = max(diameter, left + right); return 1 + max(left, right) }; _ = height(root); return diameter } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1/L2 (recurse)	$O(1)$ dispatch	n	$O(n)$
L3 (update diameter)	$O(1)$	n	$O(n)$
L4 (return height)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Each node is visited exactly once. The side-effect at L3 accumulates the global answer without requiring a second pass.

Complexity

• Time: $O(n)$, driven by L1/L2 visiting every node once.
• Space: $O(h)$ recursion depth.

Pattern: “side-effect accumulator during a DFS that returns something else”

This is the template for a whole class of tree problems, including 124 Max Path Sum, 1245 Tree Diameter, and many others. The DFS returns a “local contribution to the parent” (here, the height), and the diameter is updated as a side effect based on the combined contributions from both children.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
For each node, recompute heights	$O(n²)$	$O(h)$
Single DFS with accumulator	$O(n)$	$O(h)$

There’s no meaningful middle tier here, this is the jump from “obvious recursive statement” to the realization that you can compute height and update diameter in one DFS.

Test cases

Python

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def diameter_of_binary_tree(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)
    height(root)
    return best

def _run_tests():
    assert diameter_of_binary_tree(build_tree([1, 2, 3, 4, 5])) == 3
    assert diameter_of_binary_tree(build_tree([1, 2])) == 1
    assert diameter_of_binary_tree(build_tree([1])) == 0
    # skewed tree: diameter = n-1 edges
    t = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
    assert diameter_of_binary_tree(t) == 3
    # diameter through node 2 (both children): [1,2,null,3,4]
    t2 = build_tree([1, 2, None, 3, 4])
    assert diameter_of_binary_tree(t2) == 2  # path 3->2->4, both at depth 1 from 2
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function diameterOfBinaryTree(root: TreeNode | null): number {
    let best = 0;
    function height(node: TreeNode | null): number {
        if (!node) return 0;
        const left = height(node.left);
        const right = height(node.right);
        best = Math.max(best, left + right);
        return 1 + Math.max(left, right);
    }
    height(root);
    return best;
}

console.assert(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])) === 3);
console.assert(diameterOfBinaryTree(buildTree([1, 2])) === 1);
console.assert(diameterOfBinaryTree(buildTree([1])) === 0);
const t = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4))));
console.assert(diameterOfBinaryTree(t) === 3);
const t2 = buildTree([1, 2, null, 3, 4]);
console.assert(diameterOfBinaryTree(t2) === 2);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, height + accumulator DFS

Related concepts

• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
• DFS, the depth first traversal habit of following one branch before returning.