Binary Tree Longest Consecutive Sequence

medium tree dfs

Problem

Find the length of the longest consecutive (strictly increasing by 1) sequence in a binary tree that follows the parent-child connection.

Inputroot = [1,null,3,2,4,null,null,null,5]

Output3

3 → 4 → 5 is the longest run.

tree (level-order, 'n' for null)

def longest_consecutive(root):
    best = 0
    def dfs(node, parent, length):
        nonlocal best
        if not node: return
        length = length + 1 if parent is not None and node.val == parent + 1 else 1
        best = max(best, length)
        dfs(node.left, node.val, length)
        dfs(node.right, node.val, length)
    dfs(root, None, 0)
    return best

function longestConsecutive(root) {
  let best = 0;
  function dfs(node, parent, len) {
    if (!node) return;
    len = (parent !== null && node.val === parent + 1) ? len + 1 : 1;
    best = Math.max(best, len);
    dfs(node.left, node.val, len);
    dfs(node.right, node.val, len);
  }
  dfs(root, null, 0);
  return best;
}

class Solution {
    int best = 0;
    public int longestConsecutive(TreeNode root) { dfs(root, null, 0); return best; }
    void dfs(TreeNode node, Integer parent, int len) {
        if (node == null) return;
        len = (parent != null && node.val == parent + 1) ? len + 1 : 1;
        best = Math.max(best, len);
        dfs(node.left, node.val, len);
        dfs(node.right, node.val, len);
    }
}

class Solution {
    int best = 0;
    void dfs(TreeNode* n, int parent, bool hasParent, int len) {
        if (!n) return;
        len = (hasParent && n->val == parent + 1) ? len + 1 : 1;
        best = max(best, len);
        dfs(n->left, n->val, true, len);
        dfs(n->right, n->val, true, len);
    }
public:
    int longestConsecutive(TreeNode* root) { dfs(root, 0, false, 0); return best; }
};

Explanation

Here a consecutive run must go strictly top-down, following parent to child and increasing by exactly 1 each step. The neat idea is to carry the current run length down the recursion as we go.

The helper dfs(node, parent, length) looks at the parent's value. If node.val == parent + 1, the run continues, so we set length = length + 1. Otherwise the chain breaks here and we restart at 1.

At every node we update a global best = max(best, length), then recurse into both children passing the node's own value as the new parent. This single DFS naturally tries every downward chain.

Example: in 1 → 3 → 2 → 4 → 5 shaped tree, the chain 3 → 4 → 5 works. At 3 length is 1, at 4 (since 4 == 3 + 1) length becomes 2, at 5 it becomes 3, so best = 3.

Each node is touched once doing constant work, giving O(n) time and O(h) stack space for the recursion.

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