> For the complete documentation index, see [llms.txt](https://snowan.gitbook.io/study-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://snowan.gitbook.io/study-notes/leetcode/30daychallenge/check-string-valid-sequence-from-root-to-leaves-path-in-bst.md).

# 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](https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/532/week-5/3315/)

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

![example 1](/files/-M6DkyVPbc2DVCnQauZY)

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

![example 2](/files/-M6DkyVQsnKk2GwgqzEb)

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

![example 3](/files/-M6DkyVRjudmetOxefG5)

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

![Valid String Sequence from Root to Leaves DFS](/files/-M6DkyVSms4n-7Du7LLR)

### Complexity Analysis

**Time Complexity:** `O(N)`

* N - Number of nodes&#x20;

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

![Valid String Sequence from Root to Leaves BFS](/files/-M6DkyVTeeniyXf0pQAv)

```
class Solution {
    public boolean isValidSequence(TreeNode root, int[] arr) {
        if (arr == null || arr.length == 0) return true;
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        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++;
        }

        // not found
        return false;
    }
}
```