Path With Given Sequence (Does a Root-to-Leaf Path Match an Exact Sequence?)

• Path With Given Sequence checks if any root-to-leaf path matches a fixed target sequence in both order and length.
• Index tracking carries a position pointer into the sequence, advancing it at each node whose value matches.
• Three-way guard rejects immediately on null node, index out of range, or value mismatch.
• Exact-length rule requires the match to consume the full sequence at a leaf, rejecting both prefix-only and incomplete paths.
• Time is O(n) because each node is visited at most once; space is O(h) for the call stack.

What is the Path With Given Sequence problem?

You are given a binary tree and an integer array representing a target sequence. The task is to determine whether any root-to-leaf path in the tree has node values that match the sequence exactly, in order and in length. This is a Tree DFS problem where an index pointer tracks how far into the sequence you have matched.

package com.bank.service;

public class SequencePathValidator {
    public boolean hasPath(TreeNode root, int[] sequence) {
        if (root == null) return sequence.length == 0;
        return dfs(root, sequence, 0);
    }
}

Why does this problem exist?

In banking workflows, certain transactions must follow an exact routing path through a hierarchy of departments. The compliance team defines a mandated sequence of department codes, and the system must verify that a real routing path through the tree matches that sequence exactly. Any deviation, whether a missing step, an extra step, or a wrong code, is a compliance failure.

How does the index-tracking DFS work?

The DFS carries an integer index that tracks how far into the target sequence we have matched. At each node, three conditions can cause immediate rejection: the node is null, the index has overrun the sequence length, or the node value does not match the sequence element at the current index.

private boolean dfs(TreeNode node, int[] seq, int index) {
    // Guard: reject impossible states
    if (node == null || index >= seq.length || node.val != seq[index]) {
        return false;
    }

    // Success: leaf node and index is at the last element
    if (node.left == null && node.right == null
            && index == seq.length - 1) {
        return true;
    }

    // Recurse: try both children with index advanced
    return dfs(node.left, seq, index + 1)
        || dfs(node.right, seq, index + 1);
}

Example:
  Tree:      1          Sequence: [1, 9, 1]
            / \
           7    9
              / \
             2    1

  Path [1,9,1] exists at root→right→right. Result: true
  Path [1,7] does NOT match [1,9,1] because value 7 != 9.

Why must the match be exact in length?

A path that matches the sequence as a prefix but continues past it is not valid. For example, if the sequence is [1, 9] but the path continues to a child node after 9, the leaf check fails because the index is not at the last position when the node is still internal. A path that ends before consuming the sequence is also rejected because the leaf test requires index == seq.length - 1.

// Sequence = [1, 9], but path is [1, 9, 2]
// At node 9: index = 1, seq.length - 1 = 1, BUT node 9 is not a leaf.
// So we recurse deeper. At node 2: index = 2, which >= seq.length.
// Guard rejects. Result: false. The prefix match is NOT accepted.

// Sequence = [1, 9, 2, 5], but path is [1, 9, 2]
// At leaf node 2: index = 2, seq.length - 1 = 3.
// index != seq.length - 1, so leaf check fails. Result: false.

How is this different from Path Sum?

Path Sum checks if values add up to a target. Path With Given Sequence checks if values match a fixed ordered array element by element. Path Sum allows different paths with different node values as long as the sum matches. Path With Given Sequence requires exact value-by-value correspondence.

| Aspect | Path Sum | Path With Given Sequence |
|--------|----------|-------------------------|
| Check | Sum of values == target | Values match array element-by-element |
| Tracking | Running sum | Index into array |
| Flexibility | Any values that sum correctly | Exact values in exact order |
| Length constraint | Must be root-to-leaf | Must be root-to-leaf AND match array length |

What are edge cases?

• Empty tree with empty sequence: return true (both are empty, so they match).
• Empty tree with non-empty sequence: return false.
• Single-node tree with sequence of length 1: return true if values match, false otherwise.
• Sequence longer than the tree height: every path fails the index guard before reaching a leaf.

// Edge case: single node
// Tree = [5], Sequence = [5]
// Node 5 is a leaf, index 0 == seq.length - 1 (0). Values match.
// Result: true

// Edge case: sequence longer than any path
// Tree = [1, 2, 3], max depth = 2
// Sequence = [1, 2, 3, 4], length = 4
// No path can consume all 4 elements. Result: false

What are common mistakes?

The first mistake is forgetting to check the leaf condition and returning true whenever the index reaches the last position, even at an internal node. This would incorrectly accept prefix matches. The second mistake is checking index == seq.length instead of index == seq.length - 1, which is an off-by-one error because the index is zero-based.

// WRONG: accepts internal nodes as matches
if (index == seq.length - 1) return true;  // missing leaf check!

// CORRECT: requires both leaf and full consumption
if (node.left == null && node.right == null && index == seq.length - 1)
    return true;

What about short-circuit evaluation?

The OR operator in the recursive case means the first matching path stops the search. Once the left subtree returns true, the right subtree is never explored. This is efficient because we only need one matching path, not all of them.

// Short-circuit: if left finds a match, right is skipped
return dfs(node.left, seq, index + 1)
    || dfs(node.right, seq, index + 1);

What is the time and space complexity?

Time is O(n) because each node is visited at most once. The three-way guard prunes mismatched branches early, so in practice the algorithm often visits far fewer nodes. Space is O(h) for the recursion stack, where h is the tree height: O(log n) for a balanced tree and O(n) for a skewed tree.

What should a senior engineer know?

The combined guard node == null || index >= seq.length || node.val != seq[index] is a clean pattern that handles all failure modes in one line. Breaking it into separate checks is valid but verbose. The order of checks matters: null must come first to avoid a NullPointerException, and the index check must come before the value access to avoid an ArrayIndexOutOfBoundsException.

In production systems at the National Bank of India, Rajesh used this pattern to validate mandated routing for high-value payments, where each payment had to traverse an exact regulator-approved sequence of desk codes. The DFS with index tracking confirmed compliance in a single pass through the hierarchy.