Longest Path in a Binary Tree | Practice

You are given root, the root of a non-empty binary tree.

Return the length of the longest path between any two nodes, counted in edges (the links between a parent and a child). A path never visits a node twice, and it need not pass through the root.

Trees are written in level order, row by row from the top, with null where a node is missing: [4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.

Example 1

Input: root = [8, 3, 10, 1, 6, null, 14]
Output: 4

One longest path is 1 → 3 → 8 → 10 → 14, which has four edges.

Example 2

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

The longest path, 7 → 5 → 3 → 2 → 4 → 6 → 8, turns at 2 and never reaches the root.

Constraints

The tree holds 1 to 1000 nodes.
Every value is between −100 and 100.

Show the pattern

Trees

The longest path turns at some highest node and runs down both of its sides, so its length is that node's left height plus its right height. One depth-first pass computes every height and keeps the best sum along the way.

See trees in a visualiser

Show the approach

Every path has a highest node, where it turns. The longest path turning at a node runs down to the deepest node on each side, so its length in edges is height(left) + height(right), where a subtree's height counts the nodes on its longest downward path (0 for an empty one).

A post-order recursion returns each subtree's height, 1 + max(left, right), and at every node updates the best left + right seen so far. That best value is the answer.

Time: O(n) · Space: O(h) for the recursion, h the tree's height

Brush up firstBinary Search Tree visualiser