Problem

Given a binary tree where each path going from the root to any leaf form a valid sequence , check if a given string is a valid sequence in such binary tree.

We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.

Examples

Example 1:

1
2
3
4
5
6

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). 
Other valid sequences are: 
0 -> 1 -> 1 -> 0 
0 -> 0 -> 0

Example 2: 

1
2
3

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
Output: false 
Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.

Example 3: 

1
2
3

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
Output: false
Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a valid sequence.

Constraints:

  • 1 <= arr.length <= 5000
  • 0 <= arr[i] <= 9
  • Each node’s value is between [0 - 9].

Solution

Method 1 – Depth-First Search (DFS) Path Matching

Intuition

We need to check if there exists a root-to-leaf path in the binary tree such that the sequence of node values matches the given array. This is a classic DFS problem where we match the current node’s value with the current index in the array and recursively check the left and right subtrees.

Approach

  1. Start DFS from the root node and index 0 of the array.
  2. At each node:
    • If the node is null or the index is out of bounds, return false.
    • If the node’s value does not match arr[index], return false.
    • If at a leaf node and index is at the last element of arr, return true.
    • Recursively check left and right children with index + 1.
  3. Return true if any path matches, else false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isValidSequence(root *TreeNode, arr []int) bool {
    var dfs func(node *TreeNode, idx int) bool
    dfs = func(node *TreeNode, idx int) bool {
        if node == nil || idx >= len(arr) || node.Val != arr[idx] {
            return false
        }
        if node.Left == nil && node.Right == nil && idx == len(arr)-1 {
            return true
        }
        return dfs(node.Left, idx+1) || dfs(node.Right, idx+1)
    }
    return dfs(root, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun isValidSequence(root: TreeNode?, arr: IntArray): Boolean {
        fun dfs(node: TreeNode?, idx: Int): Boolean {
            if (node == null || idx >= arr.size || node.`val` != arr[idx]) return false
            if (node.left == null && node.right == null && idx == arr.size - 1) return true
            return dfs(node.left, idx + 1) || dfs(node.right, idx + 1)
        }
        return dfs(root, 0)
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def isValidSequence(self, root: 'TreeNode', arr: list[int]) -> bool:
        def dfs(node: 'TreeNode', idx: int) -> bool:
            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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn is_valid_sequence(root: Option<Rc<RefCell<TreeNode>>>, arr: Vec<i32>) -> bool {
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, arr: &Vec<i32>, idx: usize) -> bool {
            if node.is_none() || idx >= arr.len() { return false; }
            let n = node.as_ref().unwrap().borrow();
            if n.val != arr[idx] { return false; }
            if n.left.is_none() && n.right.is_none() && idx == arr.len() - 1 { return true; }
            dfs(n.left.clone(), arr, idx + 1) || dfs(n.right.clone(), arr, idx + 1)
        }
        dfs(root, &arr, 0)
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the tree.
  • 🧺 Space complexity: O(h), where h is the height of the tree (recursion stack).