Diameter of Binary Tree

The problem

A binary tree is made of nodes. Each node has a value, val, and two children, left and right; a missing child is null. You are given root, the top node, or null for an empty tree. An edge is the link between a node and one of its children. A path goes from one node to another along edges, never visiting a node twice. The diameter is the number of edges on the longest path in the tree. That path may join any two nodes and does not have to pass through the root. Return the diameter. An empty tree or a single node has diameter 0.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(root: TreeNode | null): number

Input
root = {"val":1,"left":{"val":2,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}},"right":{"val":3,"left":null,"right":null}}

Output
3

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":null}

Output
1

Constraints

Trees use {val, left, right}.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Count edges, not nodes: a path over four nodes has three edges, and a single node has diameter 0. The longest path does not have to pass through the root, so looking only at the root is not enough.

2. Hint 2: Ask a smaller question

   In example 1 the longest path joins node 4 and node 3. Which node on that path is highest in the tree, and how many edges of the path lie on each side of that node? Answer the same two questions for the path from node 4 to node 5.

3. Hint 3: Name the pattern

   Every path has one highest node. The longest path with a given highest node runs down both sides of it as far as possible. That distance down is a height, which a node gets from its children's heights. Children answer first: postorder tree recursion. A helper that calls itself promises, for any node, the height of the tree starting there. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   Count a height in nodes, 0 for a missing child. Then left height plus right height is exactly the number of edges on the longest path whose highest node is this one. The diameter is the largest such sum over all the nodes.

5. Hint 5: Sketch the pseudocode

   Keep a best length, starting at 0. Height of a node: if it is null, return 0. Get the left height and the right height with the same function. If their sum is larger than best, store it. Return 1 plus the larger height. Call this on the root, then return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Postorder traversal returns heights; adding the two child heights gives the longest path through each node.

The slow way

At every node, measure how far down the tree goes on its left and on its right, each time from scratch, add the two, and keep the largest sum. It is correct, but each measurement walks part of the tree again. On a tree that is one long chain of n nodes, that adds up to about n × n / 2 steps.

The insight

How far down a tree goes is its height. A function that computes heights already holds, at every node, the two numbers a path needs: the height on the node's left and the height on its right. So one walk can do both jobs. It reports heights upward, children before parents, which is what postorder means, and remembers the largest sum of the two heights.

Step by step

1. Keep the length of the longest path found so far, starting at 0. The longest path can have any node as its highest point, so one best length is kept for the whole walk, outside the function that does the walking. An empty tree or a single node leaves that length at 0.
2. A helper returns the height of a subtree, 0 for an empty one. The helper is a function inside the main one. A subtree is a child with everything below that child. Its height is the number of nodes on its longest way down: 0 for a missing child, where the calls stop.
3. Ask for the heights of the left and the right subtree. The helper calls itself, which is called recursion, and it promises the height of any subtree it is given. Both numbers are used twice below: added together for the path, and compared for this node's own height.
4. Add the two heights and keep the sum if it is the longest so far. The longest path whose highest point is this node runs down each side as far as it can. A side that is 2 nodes high takes 2 edges to walk down, so the two heights added give the path's edges.
5. Return this subtree's height: one more than the taller side. The parent asked for a height, not for a path. A path that goes on up to the parent can use only one side of this node, so only the taller side counts, plus 1 for the node itself.
6. Run the helper on the root, then return the longest length found. Starting at the root makes the helper visit every node, so every possible highest point has been tried. The helper's own result, the root's height, is not the answer and is ignored.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. Keep the length of the longest path found so far, starting at 0
  let best = 0;
  // 2. A helper returns the height of a subtree, 0 for an empty one
  function height(node) {
    if (!node) return 0;
    // 3. Ask for the heights of the left and the right subtree
    const left = height(node.left);
    const right = height(node.right);
    // 4. Add the two heights and keep the sum if it is the longest so far
    best = Math.max(best, left + right);
    // 5. Return this subtree's height: one more than the taller side
    return 1 + Math.max(left, right);
  }
  // 6. Run the helper on the root, then return the longest length found
  height(root);
  return best;
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(root: TreeNode | null): number {
  // 1. Keep the length of the longest path found so far, starting at 0
  let best = 0;
  // 2. A helper returns the height of a subtree, 0 for an empty one
  function height(node: TreeNode | null): number {
    if (!node) return 0;
    // 3. Ask for the heights of the left and the right subtree
    const left = height(node.left);
    const right = height(node.right);
    // 4. Add the two heights and keep the sum if it is the longest so far
    best = Math.max(best, left + right);
    // 5. Return this subtree's height: one more than the taller side
    return 1 + Math.max(left, right);
  }
  // 6. Run the helper on the root, then return the longest length found
  height(root);
  return best;
}

def solve(root):
    # 1. Keep the length of the longest path found so far, starting at 0
    best = 0

    # 2. A helper returns the height of a subtree, 0 for an empty one
    def height(node):
        # Python needs this line before the helper may change best.
        nonlocal best
        if node is None:
            return 0
        # 3. Ask for the heights of the left and the right subtree
        left = height(node.left)
        right = height(node.right)
        # 4. Add the two heights and keep the sum if it is the longest so far
        best = max(best, left + right)
        # 5. Return this subtree's height: one more than the taller side
        return 1 + max(left, right)

    # 6. Run the helper on the root, then return the longest length found
    height(root)
    return best

Example 1, traced

Input
root = {"val":1,"left":{"val":2,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}},"right":{"val":3,"left":null,"right":null}}

Output
3

Why it works

Every path has exactly one highest node. Among the paths with the same highest node, the longest runs down as far as possible on both sides, which is left height plus right height edges. The helper computes that sum at every node and keeps the largest, so the longest path in the whole tree is among the sums it has seen.

Time and space

Time O(n), extra space O(h). The helper runs once per node and once per missing child, with constant work each time: O(n) time in one walk. The unfinished calls form a chain from the root down, one per level: O(h) on the call stack for a tree of height h.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Return the longest length found, not the helper's result, which is the root's height. In example 1 both happen to be 3, but in example 2 the height is 2 and the diameter is 1.
• Do not measure at the root only. The longest path can lie inside one subtree, for example when the root has a single child and that child has a long branch on each side.
• Hand the parent a height, 1 plus the taller side, not 1 plus both sides. A path cannot go down both sides of a node and also continue upward. With both sides, example 1 gives 4.

Pattern

Postorder tree recursion. Builds on Maximum Depth of Binary Tree.

Keep going