Binary Tree Longest Consecutive Sequence II

medium tree dfs

Problem

Find the length of the longest consecutive path in a binary tree. The path can go child-parent-child (so it does not need to be top-down), and values must differ by exactly 1 between consecutive nodes.

Inputroot = [2,1,3]

Output3

Path 1 → 2 → 3 routes through the root (1 increasing left, 2 increasing right).

tree (level-order, "null" allowed)

def longest_consecutive(root):
    best = 0
    def dfs(n):
        nonlocal best
        if not n: return (0, 0)
        inc, dec = 1, 1
        for child, di, dd in ((n.left, 0, 0), (n.right, 0, 0)):
            if not child: continue
            ci, cd = dfs(child)
            if child.val == n.val + 1: inc = max(inc, ci + 1)
            if child.val == n.val - 1: dec = max(dec, cd + 1)
        best = max(best, inc + dec - 1)
        return (inc, dec)
    dfs(root)
    return best

function longestConsecutive(root) {
  let best = 0;
  function dfs(n) {
    if (!n) return [0, 0];
    let inc = 1, dec = 1;
    for (const c of [n.left, n.right]) {
      if (!c) continue;
      const [ci, cd] = dfs(c);
      if (c.val === n.val + 1) inc = Math.max(inc, ci + 1);
      if (c.val === n.val - 1) dec = Math.max(dec, cd + 1);
    }
    best = Math.max(best, inc + dec - 1);
    return [inc, dec];
  }
  dfs(root);
  return best;
}

class Solution {
    int best = 0;
    public int longestConsecutive(TreeNode root) { dfs(root); return best; }
    int[] dfs(TreeNode n) {
        if (n == null) return new int[]{0, 0};
        int inc = 1, dec = 1;
        for (TreeNode c : new TreeNode[]{n.left, n.right}) {
            if (c == null) continue;
            int[] r = dfs(c);
            if (c.val == n.val + 1) inc = Math.max(inc, r[0] + 1);
            if (c.val == n.val - 1) dec = Math.max(dec, r[1] + 1);
        }
        best = Math.max(best, inc + dec - 1);
        return new int[]{inc, dec};
    }
}

int best = 0;
pair<int,int> dfs(TreeNode* n) {
    if (!n) return {0, 0};
    int inc = 1, dec = 1;
    for (auto c : {n->left, n->right}) {
        if (!c) continue;
        auto r = dfs(c);
        if (c->val == n->val + 1) inc = max(inc, r.first + 1);
        if (c->val == n->val - 1) dec = max(dec, r.second + 1);
    }
    best = max(best, inc + dec - 1);
    return {inc, dec};
}
int longestConsecutive(TreeNode* root) { best = 0; dfs(root); return best; }

Explanation

This problem allows a consecutive path to bend at a node, going up one side and down the other (child-parent-child). The clever trick is that each node reports back two numbers, so its parent can decide how to combine them.

The recursion dfs(n) returns a pair (inc, dec): the longest increasing run that ends going down from n, and the longest decreasing run. For each child, if child.val == n.val + 1 the increasing run can extend, and if child.val == n.val - 1 the decreasing run can extend.

The longest path that passes through n is an increasing arm coming up to n joined with a decreasing arm going down, which is inc + dec - 1 (we subtract 1 because n itself is counted in both arms). We keep a global best of this across all nodes.

Example: tree [2, 1, 3]. At leaf 1 we get (1, 1); at leaf 3 also (1, 1). At root 2, child 1 is 2 - 1 so dec = 2, and child 3 is 2 + 1 so inc = 2. The through-path is 2 + 2 - 1 = 3, matching the run 1 → 2 → 3.

Because every node is visited once and only does constant work, the whole thing runs in O(n) time.

Time: O(n) Space: O(h) recursion