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

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



/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidSequence(TreeNode root, int[] arr) {
       
        return checkPath(root, arr, 0);
       
    }
   
     private static boolean checkPath(TreeNode root, int arr[], int index)
    {
         if(root == null || index == arr.length)
             return false;
        
         if(root.left == null && root.right == null && root.val == arr[index] && index == arr.length-1)
             return true;
       
         return root.val == arr[index] && (checkPath(root.left, arr, index+1) || checkPath(root.right, arr, index+1));
   
    }
}


 Try it on Leetcode

Here, the path must start from root and last element in array must be a leaf.

In method,
1) If root is null or index is length of array then it false.

2) We have to find leaf node. For that, if root left, right are null and root.val is equal to number at that index of array then we have to return true.

3)Else if root value is find in array, then we have to recur left subtree from next index.
    a) If left subtree recur fails, then do right recur to find path.

Please let us know your views in comment section.