Check if there is a root to leaf path with given sequence | Java program to see if there is a root to leaf path with given sequence . ; A binary tree node has data , pointer to left child and a pointer to right child ; Util function ; If root is NULL or reached end of the array ; If current node is leaf ; If current node is equal to arr [ index ] this means that till this level path has been matched and remaining path can be either in left subtree or right subtree . ; Function to check given sequence of root to leaf path exist in tree or not . index : current element in sequence of root to leaf path ; Driver code ; arr [ ] : sequence of root to leaf path
import java . io . * ; class Node { int data ; Node left ; Node right ; Node ( int data ) { this . data = data ; this . left = null ; this . right = null ; } } class GFG { static boolean existPathUtil ( Node root , int arr [ ] , int n , int index ) { if ( root == null index == n ) return false ; if ( root . left == null && root . right == null ) { if ( ( root . data == arr [ index ] ) && ( index == n - 1 ) ) return true ; return false ; } return ( ( index < n ) && ( root . data == arr [ index ] ) && ( existPathUtil ( root . left , arr , n , index + 1 ) || existPathUtil ( root . right , arr , n , index + 1 ) ) ) ; } static boolean existPath ( Node root , int arr [ ] , int n , int index ) { if ( root == null ) return ( n == 0 ) ; return existPathUtil ( root , arr , n , 0 ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 8 , 6 , 7 } ; int n = arr . length ; Node root = new Node ( 5 ) ; root . left = new Node ( 3 ) ; root . right = new Node ( 8 ) ; root . left . left = new Node ( 2 ) ; root . left . right = new Node ( 4 ) ; root . left . left . left = new Node ( 1 ) ; root . right . left = new Node ( 6 ) ; root . right . left . right = new Node ( 7 ) ; if ( existPath ( root , arr , n , 0 ) ) System . out . println ( " Path ▁ Exists " ) ; else System . out . println ( " Path ▁ does ▁ not ▁ Exist " ) ; } }