Construct Tree from given Inorder and Preorder traversals | C # program to construct a tree using inorder and preorder traversal ; Function to build tree using given traversal ; Function to print tree in Inorder ; first recur on left child ; then print the data of node ; now recur on right child ; Driver Code
using System ; using System . Collections . Generic ; public class TreeNode { public int val ; public TreeNode left ; public TreeNode right ; public TreeNode ( int x ) { val = x ; } } class GFG { static HashSet < TreeNode > set = new HashSet < TreeNode > ( ) ; static Stack < TreeNode > stack = new Stack < TreeNode > ( ) ; public TreeNode buildTree ( int [ ] preorder , int [ ] inorder ) { TreeNode root = null ; for ( int pre = 0 , iN = 0 ; pre < preorder . Length ; ) { TreeNode node = null ; do { node = new TreeNode ( preorder [ pre ] ) ; if ( root == null ) { root = node ; } if ( stack . Count != 0 ) { if ( set . Contains ( stack . Peek ( ) ) ) { set . Remove ( stack . Peek ( ) ) ; stack . Pop ( ) . right = node ; } else { stack . Peek ( ) . left = node ; } } stack . Push ( node ) ; } while ( preorder [ pre ++ ] != inorder [ iN ] && pre < preorder . Length ) ; node = null ; while ( stack . Count != 0 && iN < inorder . Length && stack . Peek ( ) . val == inorder [ iN ] ) { node = stack . Pop ( ) ; iN ++ ; } if ( node != null ) { set . Add ( node ) ; stack . Push ( node ) ; } } return root ; } void printInorder ( TreeNode node ) { if ( node == null ) return ; printInorder ( node . left ) ; Console . Write ( node . val + " ▁ " ) ; printInorder ( node . right ) ; } public static void Main ( String [ ] args ) { GFG tree = new GFG ( ) ; int [ ] iN = new int [ ] { 9 , 8 , 4 , 2 , 10 , 5 , 10 , 1 , 6 , 3 , 13 , 12 , 7 } ; int [ ] pre = new int [ ] { 1 , 2 , 4 , 8 , 9 , 5 , 10 , 10 , 3 , 6 , 7 , 12 , 13 } ; int len = iN . Length ; TreeNode root = tree . buildTree ( pre , iN ) ; tree . printInorder ( root ) ; } }