Check if given sorted sub | Java program to find if given array exists as a subsequece in BST ; A binary Tree node ; structure of int class ; A utility function to create a new BST node with key as given num ; A utility function to insert a given key to BST ; function to check if given sorted sub - sequence exist in BST index - . iterator for given sorted sub - sequence seq [ ] - . given sorted sub - sequence ; We traverse left subtree first in Inorder ; If current node matches with se [ index ] then move forward in sub - sequence ; We traverse left subtree in the end in Inorder ; A wrapper over seqExistUtil . It returns true if seq [ 0. . n - 1 ] exists in tree . ; Initialize index in seq [ ] ; Do an inorder traversal and find if all elements of seq [ ] were present ; index would become n if all elements of seq [ ] were present ; Driver code
import java . util . * ; class GFG { static class Node { int data ; Node left , right ; } ; static class INT { int a ; } static Node newNode ( int num ) { Node temp = new Node ( ) ; temp . data = num ; temp . left = temp . right = null ; return temp ; } static Node insert ( Node root , int key ) { if ( root == null ) return newNode ( key ) ; if ( root . data > key ) root . left = insert ( root . left , key ) ; else root . right = insert ( root . right , key ) ; return root ; } static void seqExistUtil ( Node ptr , int seq [ ] , INT index ) { if ( ptr == null ) return ; seqExistUtil ( ptr . left , seq , index ) ; if ( ptr . data == seq [ index . a ] ) index . a ++ ; seqExistUtil ( ptr . right , seq , index ) ; } static boolean seqExist ( Node root , int seq [ ] , int n ) { INT index = new INT ( ) ; index . a = 0 ; seqExistUtil ( root , seq , index ) ; return ( index . a == n ) ; } public static void main ( String args [ ] ) { Node root = null ; root = insert ( root , 8 ) ; root = insert ( root , 10 ) ; root = insert ( root , 3 ) ; root = insert ( root , 6 ) ; root = insert ( root , 1 ) ; root = insert ( root , 4 ) ; root = insert ( root , 7 ) ; root = insert ( root , 14 ) ; root = insert ( root , 13 ) ; int seq [ ] = { 4 , 6 , 8 , 14 } ; int n = seq . length ; if ( seqExist ( root , seq , n ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }