# check-string-valid-sequence-from-root-to-leaves-path-in-bst

## Problem

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

## Problem Description

``````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.

Example 1:``````
``````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:

``````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:``````
``````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

DFS, check root to leaf every path, compare with arr, if found return true. otherwise return false.

for example:

### Complexity Analysis

Time Complexity: `O(N)`

• N - Number of nodes

### Code

DFS Java code

``````class Solution {
public boolean isValidSequence(TreeNode root, int[] arr) {
if (arr == null || arr.length == 0) return true;
if (root == null) return false;
return dfs(root, 0, arr);
}

private boolean dfs(TreeNode node, int idx, int[] arr) {
// node is null or already reached to end of arr, false
if (node == null || idx == arr.length) return false;
// reach to end of arr and equal to current node value
if (idx == arr.length - 1 && arr[idx] == node.val) {
// check whether it is leaf
return node.left == null && node.right == null;
}
// not reach to leaf or end of arr, continue check left or right
return idx < arr.length && node.val == arr[idx]
&& (dfs(node.left, idx + 1, arr) || dfs(node.right, idx + 1, arr));
}
}``````

BFS Java Code

Using BFS, sweep each level and compare with arr[idx], if idx at last index of arr and current node is leaf, then found valid sequence. otherwise continue.

For example:

``````class Solution {
public boolean isValidSequence(TreeNode root, int[] arr) {
if (arr == null || arr.length == 0) return true;
if (root == null) return false;
queue.offer(root);
int idx = 0;
int len = arr.length;
while (!queue.isEmpty() && idx < len) {
int size = queue.size();
int num = arr[idx];
while (size-- > 0) {
TreeNode node = queue.poll();
if (num != node.val) continue;
// last index of arr, and current node is leaf, return true
if (idx == len - 1 && node.left == null && node.right == null) return true;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
idx++;
}