Leaf nodes from Preorder of a Binary Search Tree | C ++ program to print leaf node from preorder of binary search tree . ; Binary Search ; Point to the index in preorder . ; Function to print Leaf Nodes by doing preorder traversal of tree using preorder and inorder arrays . ; If l == r , therefore no right or left subtree . So , it must be leaf Node , print it . ; If array is out of bound , return . ; Finding the index of preorder element in inorder array using binary search . ; Incrementing the index . ; Finding on the left subtree . ; Finding on the right subtree . ; Finds leaf nodes from given preorder traversal . ; To store inorder traversal ; Copy the preorder into another array . ; Finding the inorder by sorting the array . ; Print the Leaf Nodes . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binarySearch ( int inorder [ ] , int l , int r , int d ) { int mid = ( l + r ) >> 1 ; if ( inorder [ mid ] == d ) return mid ; else if ( inorder [ mid ] > d ) return binarySearch ( inorder , l , mid - 1 , d ) ; else return binarySearch ( inorder , mid + 1 , r , d ) ; } int ind = 0 ; void leafNodesRec ( int preorder [ ] , int inorder [ ] , int l , int r , int * ind , int n ) { if ( l == r ) { printf ( " % d ▁ " , inorder [ l ] ) ; * ind = * ind + 1 ; return ; } if ( l < 0 l > r r >= n ) return ; int loc = binarySearch ( inorder , l , r , preorder [ * ind ] ) ; * ind = * ind + 1 ; leafNodesRec ( preorder , inorder , l , loc - 1 , ind , n ) ; leafNodesRec ( preorder , inorder , loc + 1 , r , ind , n ) ; } void leafNodes ( int preorder [ ] , int n ) { int inorder [ n ] ; for ( int i = 0 ; i < n ; i ++ ) inorder [ i ] = preorder [ i ] ; sort ( inorder , inorder + n ) ; leafNodesRec ( preorder , inorder , 0 , n - 1 , & ind , n ) ; } int main ( ) { int preorder [ ] = { 890 , 325 , 290 , 530 , 965 } ; int n = sizeof ( preorder ) / sizeof ( preorder [ 0 ] ) ; leafNodes ( preorder , n ) ; return 0 ; }