[GFG] Check if there is a root to leaf path with given sequence

Problem: Given a binary tree and an array, the task is to find if the given array sequence is present as a root to leaf path in given tree.

Example:

Input: arr= [5,2,4,8]
Output: true

Input: root = [5,2,4]
Output: false

Approach: We can use preorder traversal here. Please have a look at implementation to understand the approach as it is straight forward problem to solve.

Implementation in C#:

        public bool IsValidSequence(int[] arr)

        {

            int length = arr?.Length ?? 0;

            if (length == 0)

            {

                return true;

            }

            if (this.Root == null)

            {

                return false;

            }

            return IsValidSequence(this.Root, arr, 0);

        }

        private bool IsValidSequence(BinaryTreeNode node, int[] arr, int index)

        {

            if (index == arr.Length)

            {

                return node == null;

            }

            if (node == null || node.Value != arr[index])

            { 

                return false;

            }

            return this.IsValidSequence(node.LeftNode, arr, index + 1) || this.IsValidSequence(node.RightNode, arr, index + 1);

        }

Complexity: O(n)