# 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](https://388701358-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LmDY11BLFD0Iupj9U9t%2Fsync%2Fe7212bdb45444716555d6b399d8b36fe5ae3f559.png?generation=1588311881770702\&alt=media)

```
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](https://388701358-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LmDY11BLFD0Iupj9U9t%2Fsync%2F694fa73346e5ae2e4c20b0846c4d4319dd0b9045.png?generation=1588311879938108\&alt=media)

```
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](https://388701358-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LmDY11BLFD0Iupj9U9t%2Fsync%2F279e32eb516dd68ccb927ecceca0cbda735d21ae.png?generation=1588311878795985\&alt=media)

```
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](https://388701358-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LmDY11BLFD0Iupj9U9t%2Fsync%2Fb14182486d5c0a856748a21959f6416506881b7a.png?generation=1588311882968553\&alt=media)

### 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](https://388701358-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LmDY11BLFD0Iupj9U9t%2Fsync%2F2c3d364e8c1ee9fa90161248e0b2cd41b401d3ed.png?generation=1588311887560823\&alt=media)

```
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://snowan.gitbook.io/study-notes/leetcode/30daychallenge/check-string-valid-sequence-from-root-to-leaves-path-in-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.