Problem Statement

You are given the root of a binary tree and an integer array arr.
You need to determine whether the array arr represents a valid path from the root of the tree to any leaf node.

A valid path means:

• Starting from the root, you move down to the child nodes.
• The sequence of node values you encounter exactly matches the sequence of numbers in the given array.
• The path must end at a leaf node (a node with no left or right child).

If such a path exists, return true; otherwise, return false.

---

Example

Input:

Tree:        0
            / \
           1   0
          /|   |
         0 1   0
          |   / \
          1  0   0

Array: [0,1,0,1]

Output:

true

Explanation:
There exists a root-to-leaf path 0 → 1 → 0 → 1 that matches the given array.

---

Thinking About the Problem

We are essentially trying to trace the given sequence arr through the tree:

• Start from the root and the first element of the array.
• Move down the tree level by level.
• At each node, check whether the current node’s value matches the current array element.
• If it doesn’t match, this path is invalid.
• If it matches and we’ve reached the end of the array, we must also check that this node is a leaf node.
• If all array elements are successfully matched in a path ending at a leaf, return true.

The problem can be solved efficiently using Depth-First Search (DFS) recursion.

---

Approach

1. Use recursion to explore all possible paths starting from the root.
2. At each node:
   • Check if the node is null. If yes, the path ends — return false.
   • Check if the node’s value matches the current element of the array.
     • If not, return false.
   • If this is the last element in the array:
     • Check if this node is a leaf node.
       If yes, return true; otherwise, return false.
   • Recursively move to the left and right children with the next index of the array.
3. If any recursive call returns true, that means a valid path is found.

---

Java Code Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public boolean isValidSequence(TreeNode root, int[] arr) {
        return checkPath(root, arr, 0);
    }

    private boolean checkPath(TreeNode node, int[] arr, int index) {
        // If node is null or index is out of bounds
        if (node == null || index >= arr.length) {
            return false;
        }

        // Value mismatch
        if (node.val != arr[index]) {
            return false;
        }

        // If this is the last element in arr, check if it’s a leaf
        if (index == arr.length - 1) {
            return node.left == null && node.right == null;
        }

        // Recur for left and right children
        return checkPath(node.left, arr, index + 1) ||
               checkPath(node.right, arr, index + 1);
    }
}

---

Step-by-Step Example

Let’s consider:

Tree:        0
            / \
           1   0
          /|   |
         0 1   0
          |   / \
          1  0   0

Array: [0,1,0,1]

1. Start with root (value 0) and first array element 0.
   They match, so continue to left and right child with index = 1.
2. Left child → value 1, array[1] = 1 → match. Continue deeper.
3. Next node → value 0, array[2] = 0 → match. Continue.
4. Next node → value 1, array[3] = 1 → match, and this is the last element.
   Check if it’s a leaf — yes, it has no children.
   Return true.

Hence, a valid sequence exists.

---

Edge Cases

1. Empty Tree:
   If root is null, return false.
2. Empty Array:
   Return false because there’s no sequence to match.
3. Array Longer Than Path:
   Return false if we reach a null node before finishing the array.
4. Path Ends Before Array Ends:
   Return false if we run out of nodes before finishing the array.

---

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree.
  In the worst case, each node may be visited once.
• Space Complexity: O(H), where H is the height of the tree (recursion stack).

---

Key Takeaways

• The problem uses Depth-First Search to explore all paths.
• A valid path must exactly match the given sequence and end at a leaf.
• Recursion is natural here because at each node, we reduce the problem to checking smaller subtrees with a shorter remaining sequence.
• Always check the leaf condition when you reach the last array element.