Saltar al contenido principal

Binary Tree Longest Consecutive Sequence

Given the reference to a binary tree, return the length of the longest path in the tree that contains consecutive values.

Note: The path must move downward in the tree (from parent to child). Consecutive means each value is exactly 1 more than the previous value.

Example(s)​

Example 1:

Input:
    1
     \
      2
       \
        3

Output: 3
Explanation:
The path 1 → 2 → 3 is consecutive (1, 2, 3), length = 3.

Example 2:

Input:
       1
      / \
     2   2
    / \ / \
   4  3 5  8
     /
    4

Output: 4
Explanation:
The path 1 → 2 → 3 → 4 is consecutive (1, 2, 3, 4), length = 4.
Other paths:
- 2 → 3 → 4: length 3
- 1 → 2: length 2

Example 3:

Input:
    2
     \
      3
     /
    2
   /
  1

Output: 2
Explanation:
The longest consecutive path is 2 → 3 (length 2).
Path 3 → 2 → 1 is not consecutive (going down, not up).

Solution​

The solution uses DFS (Depth-First Search):

  1. DFS traversal: Visit each node in the tree
  2. Track consecutive length: For each node, calculate the length of consecutive sequence ending at that node
  3. Update maximum: Keep track of the maximum consecutive length seen so far
  4. Recursive calls: Pass the expected next value to children

JavaScript Solution - DFS

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Find longest consecutive sequence in binary tree
* @param {TreeNode} root - Root of the binary tree
* @return {number} - Length of longest consecutive sequence
*/
function longestConsecutive(root) {
if (!root) return 0;

let maxLength = 0;

/**
 * DFS helper function
 * @param {TreeNode} node - Current node
 * @param {number} parentVal - Value of parent node
 * @param {number} currentLength - Current consecutive length
 */
function dfs(node, parentVal, currentLength) {
  if (!node) return;
  
  // If current node continues the consecutive sequence
  if (node.val === parentVal + 1) {
    currentLength++;
  } else {
    // Start a new sequence
    currentLength = 1;
  }
  
  // Update maximum length
  maxLength = Math.max(maxLength, currentLength);
  
  // Recursively process children
  dfs(node.left, node.val, currentLength);
  dfs(node.right, node.val, currentLength);
}

// Start DFS from root (no parent, length = 1)
dfs(root, root.val - 1, 0);

return maxLength;
}

// Helper function to create a tree node
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}

// Test case 1: [1, null, 2, null, 3]
const tree1 = new TreeNode(1);
tree1.right = new TreeNode(2);
tree1.right.right = new TreeNode(3);
console.log('Example 1:', longestConsecutive(tree1)); // 3

// Test case 2: [1, 2, 2, 4, 3, 5, 8, null, 4]
const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(2);
tree2.left.left = new TreeNode(4);
tree2.left.right = new TreeNode(3);
tree2.right.left = new TreeNode(5);
tree2.right.right = new TreeNode(8);
tree2.left.right.left = new TreeNode(4);
console.log('Example 2:', longestConsecutive(tree2)); // 4

// Test case 3: [2, null, 3, 2, null, 1]
const tree3 = new TreeNode(2);
tree3.right = new TreeNode(3);
tree3.right.left = new TreeNode(2);
tree3.right.left.left = new TreeNode(1);
console.log('Example 3:', longestConsecutive(tree3)); // 2
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Returning Length)​

Here's an alternative that returns the length from each recursive call:

/**
 * Alternative: Return length from each call
 */
function longestConsecutiveAlternative(root) {
  if (!root) return 0;
  
  let maxLength = 0;
  
  function dfs(node, parentVal, length) {
    if (!node) return length;
    
    // If current node continues the sequence
    if (node.val === parentVal + 1) {
      length++;
    } else {
      length = 1;
    }
    
    maxLength = Math.max(maxLength, length);
    
    // Recursively get lengths from children
    const leftLength = dfs(node.left, node.val, length);
    const rightLength = dfs(node.right, node.val, length);
    
    return Math.max(leftLength, rightLength);
  }
  
  dfs(root, root.val - 1, 0);
  return maxLength;
}

Complexity​

  • Time Complexity: O(n) - Where n is the number of nodes. We visit each node exactly once.
  • Space Complexity: O(h) - Where h is the height of the tree. This is the space used by the recursion stack. In the worst case (skewed tree), this is O(n), but for a balanced tree it's O(log n).

Approach​

The solution uses DFS (Depth-First Search):

  1. DFS traversal: Visit each node in the tree
  2. Track consecutive length:
    • If current node's value is parentVal + 1, increment the length
    • Otherwise, start a new sequence with length 1
  3. Update maximum: Keep track of the maximum consecutive length seen
  4. Recursive calls: Process left and right children, passing the current node's value as parent value

Key Insights​

  • Downward path only: Path must go from parent to child (not upward)
  • Consecutive means +1: Each value must be exactly 1 more than the previous
  • DFS is natural: Tree traversal naturally goes downward
  • Track length per path: Each path can have different consecutive lengths
  • Update maximum: Need to track the maximum across all paths

Step-by-Step Example​

Let's trace through Example 1: Tree with nodes [1, null, 2, null, 3]

Tree:
    1
     \
      2
       \
        3

DFS traversal:

Node 1 (root):
  parentVal = 0 (root.val - 1)
  node.val = 1
  1 === 0 + 1? Yes → currentLength = 1
  maxLength = max(0, 1) = 1
  
  Process left child: null → return
  Process right child: node 2

Node 2:
  parentVal = 1
  node.val = 2
  2 === 1 + 1? Yes → currentLength = 2
  maxLength = max(1, 2) = 2
  
  Process left child: null → return
  Process right child: node 3

Node 3:
  parentVal = 2
  node.val = 3
  3 === 2 + 1? Yes → currentLength = 3
  maxLength = max(2, 3) = 3
  
  Process left child: null → return
  Process right child: null → return

Final: maxLength = 3

Let's trace through Example 2: More complex tree

Tree:
       1
      / \
     2   2
    / \ / \
   4  3 5  8
     /
    4

Key path: 1 → 2 → 3 → 4 (length 4)

DFS will explore all paths:
- 1 → 2 → 4: length 2 (1, 2, 4 - not consecutive)
- 1 → 2 → 3 → 4: length 4 (1, 2, 3, 4 - consecutive) ✓
- 1 → 2 → 5: length 2 (1, 2, 5 - not consecutive)
- 1 → 2 → 8: length 2 (1, 2, 8 - not consecutive)
- 2 → 3 → 4: length 3 (2, 3, 4 - consecutive)
- etc.

Maximum: 4

Edge Cases​

  • Empty tree: Return 0
  • Single node: Return 1
  • No consecutive sequence: Return 1 (each node is a sequence of length 1)
  • All consecutive: Return tree height
  • Multiple paths: Find the maximum across all paths
  • Disconnected sequences: Each path is independent

Important Notes​

  • Downward only: Path must go from parent to child, not child to parent
  • Consecutive means +1: Values must increase by exactly 1
  • Path independence: Each path from root to leaf is independent
  • Maximum tracking: Need to track maximum across all paths
  • DFS is optimal: Single pass through the tree
  • Longest Consecutive Sequence: Array version
  • Binary Tree Maximum Path Sum: Different path problem
  • Diameter of Binary Tree: Longest path between any two nodes
  • Path Sum: Sum of values along a path

Takeaways​

  • DFS traversal is natural for tree problems
  • Track state (parent value, current length) during traversal
  • Update maximum as we traverse
  • Path independence means each path is processed separately
  • O(n) time is optimal (must visit all nodes)