Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
        def dfs(node, idx):
            if not node or idx >= len(arr) or node.val != arr[idx]:
                return False
            if not node.left and not node.right and idx == len(arr) - 1:
                return True
            return dfs(node.left, idx + 1) or dfs(node.right, idx + 1)
        return dfs(root, 0)
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    bool isValidSequence(TreeNode* root, vector<int>& arr) {
        return dfs(root, arr, 0);
    }
    bool dfs(TreeNode* node, vector<int>& arr, int idx) {
        if (!node || idx >= arr.size() || node->val != arr[idx])
            return false;
        if (!node->left && !node->right && idx == arr.size() - 1)
            return true;
        return dfs(node->left, arr, idx + 1) || dfs(node->right, arr, idx + 1);
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {
    public boolean isValidSequence(TreeNode root, int[] arr) {
        return dfs(root, arr, 0);
    }
    private boolean dfs(TreeNode node, int[] arr, int idx) {
        if (node == null || idx >= arr.length || node.val != arr[idx])
            return false;
        if (node.left == null && node.right == null && idx == arr.length - 1)
            return true;
        return dfs(node.left, arr, idx + 1) || dfs(node.right, arr, idx + 1);
    }
}
      

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number[]} arr
 * @return {boolean}
 */
var isValidSequence = function(root, arr) {
    function dfs(node, idx) {
        if (!node || idx >= arr.length || node.val !== arr[idx])
            return false;
        if (!node.left && !node.right && idx === arr.length - 1)
            return true;
        return dfs(node.left, idx + 1) || dfs(node.right, idx + 1);
    }
    return dfs(root, 0);
};
      

Problem Description

You are given the root of a binary tree and an array of integers arr. Your task is to determine if there exists a root-to-leaf path in the tree such that the sequence of node values along this path exactly matches the given array arr.

• Each element in arr must correspond to the value of a node along the path from the root down to a leaf.
• The path must start at the root and end at a leaf node (a node with no children).
• You cannot skip or reuse nodes or elements in the array.
• Return true if there is such a path, false otherwise.

Constraints: Each node and array element is an integer. The tree and array are both non-empty.

Thought Process

To solve this problem, we need to check whether the given array arr can be matched exactly by following a path from the root of the tree to one of its leaves. This suggests a recursive approach: at each node, we check if the value matches the current element in arr, and if so, we move to the next element and the next node (either left or right).

The brute-force way would be to try every path from root to leaf and compare it to arr. However, this is unnecessary: we can prune any path as soon as we find a mismatch. This leads to a depth-first search (DFS) approach, where we only continue down paths that still match the array so far.

We also need to ensure that the path ends exactly at a leaf and that we've used all elements of arr by the time we reach the leaf.

Solution Approach

• Recursive DFS: We use a helper function (often called dfs) that takes the current node and the current index in arr as parameters.
• Base Cases:
  • If the node is null, or the index is out of bounds, or the node value doesn't match arr[idx], return false.
• Leaf Check:
  • If the current node is a leaf (no left or right child) and idx is at the last element of arr, return true.
• Recursive Step:
  • Recursively call dfs on the left and right children with idx + 1.
  • If either returns true, propagate true up the call stack.
• Why DFS? DFS is ideal because we only need to find one valid path, and we can stop searching as soon as we find it.

Example Walkthrough

Suppose the tree is:

        0
       / \
      1   0
     /|   \
    0 1    0
      / \
     0   1
    

1. Start at root (value 0), arr[0] = 0 (match).
2. Go left to node (1), arr[1] = 1 (match).
3. Go right to node (1), arr[2] = 0 (no match), so backtrack.
4. Go left to node (0), arr[2] = 0 (match).
5. Go left (null), so backtrack. Go right to node (1), arr[3] = 1 (match).
6. Node (1) is a leaf and we've used all of arr, so return true.

The function would return true for this input.

Time and Space Complexity

• Brute-force: If we tried every root-to-leaf path, in the worst case (a complete binary tree of height h), there are O(2^h) paths, and each path could be compared to arr in O(L) time (L = length of arr).
• Optimized DFS: We only visit each node at most once per position in arr, so the time complexity is O(N), where N is the number of nodes in the tree. Each recursive call processes one node and one index in arr.
• Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Summary

This problem is elegantly solved using a recursive depth-first search. By matching node values to the array as we traverse from root to leaf, and pruning paths as soon as a mismatch occurs, we ensure efficiency. The approach is both intuitive and optimal for this type of path-matching problem in binary trees, and leverages the natural structure of the tree and recursion.