Find all possible binary trees with given Inorder Traversal | C ++ program to find binary tree with given inorder traversal ; Node structure ; A utility function to create a new tree Node ; A utility function to do preorder traversal of BST ; Function for constructing all possible trees with given inorder traversal stored in an array from arr [ start ] to arr [ end ] . This function returns a vector of trees . ; List to store all possible trees ; if start > end then subtree will be empty so returning NULL in the list ; Iterating through all values from start to end for constructing left and right subtree recursively ; Constructing left subtree ; Constructing right subtree ; Now looping through all left and right subtrees and connecting them to ith root below ; Making arr [ i ] as root ; Connecting left subtree ; Connecting right subtree ; Adding this tree to list ; Driver Program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; struct Node * newNode ( int item ) { struct Node * temp = new Node ; temp -> key = item ; temp -> left = temp -> right = NULL ; return temp ; } void preorder ( Node * root ) { if ( root != NULL ) { printf ( " % d ▁ " , root -> key ) ; preorder ( root -> left ) ; preorder ( root -> right ) ; } } vector < Node * > getTrees ( int arr [ ] , int start , int end ) { vector < Node * > trees ; if ( start > end ) { trees . push_back ( NULL ) ; return trees ; } for ( int i = start ; i <= end ; i ++ ) { vector < Node * > ltrees = getTrees ( arr , start , i - 1 ) ; vector < Node * > rtrees = getTrees ( arr , i + 1 , end ) ; for ( int j = 0 ; j < ltrees . size ( ) ; j ++ ) { for ( int k = 0 ; k < rtrees . size ( ) ; k ++ ) { Node * node = newNode ( arr [ i ] ) ; node -> left = ltrees [ j ] ; node -> right = rtrees [ k ] ; trees . push_back ( node ) ; } } } return trees ; } int main ( ) { int in [ ] = { 4 , 5 , 7 } ; int n = sizeof ( in ) / sizeof ( in [ 0 ] ) ; vector < Node * > trees = getTrees ( in , 0 , n - 1 ) ; cout << " Preorder ▁ traversals ▁ of ▁ different ▁ " << " possible ▁ Binary ▁ Trees ▁ are ▁ STRNEWLINE " ; for ( int i = 0 ; i < trees . size ( ) ; i ++ ) { preorder ( trees [ i ] ) ; printf ( " STRNEWLINE " ) ; } return 0 ; }