Construct a special tree from given preorder traversal | C # program to construct a binary tree from preorder traversal ; A Binary Tree node ; A recursive function to create a Binary Tree from given pre [ ] preLN [ ] arrays . The function returns root of tree . index_ptr is used to update index values in recursive calls . index must be initially passed as 0 ; store the current value of index in pre [ ] ; Base Case : All nodes are constructed ; Allocate memory for this node and increment index for subsequent recursive calls ; If this is an internal node , construct left and right subtrees and link the subtrees ; A wrapper over constructTreeUtil ( ) ; Initialize index as 0. Value of index is used in recursion to maintain the current index in pre [ ] and preLN [ ] arrays . ; This function is used only for testing ; first recur on left child ; then print the data of node ; now recur on right child ; Driver Code
using System ; public class Node { public int data ; public Node left , right ; public Node ( int item ) { data = item ; left = right = null ; } } public class Index { public int index = 0 ; } class GFG { public Node root ; public Index myindex = new Index ( ) ; public virtual Node constructTreeUtil ( int [ ] pre , char [ ] preLN , Index index_ptr , int n , Node temp ) { int index = index_ptr . index ; if ( index == n ) { return null ; } temp = new Node ( pre [ index ] ) ; ( index_ptr . index ) ++ ; if ( preLN [ index ] == ' N ' ) { temp . left = constructTreeUtil ( pre , preLN , index_ptr , n , temp . left ) ; temp . right = constructTreeUtil ( pre , preLN , index_ptr , n , temp . right ) ; } return temp ; } public virtual Node constructTree ( int [ ] pre , char [ ] preLN , int n , Node node ) { int index = 0 ; return constructTreeUtil ( pre , preLN , myindex , n , node ) ; } public virtual void printInorder ( Node node ) { if ( node == null ) { return ; } printInorder ( node . left ) ; Console . Write ( node . data + " ▁ " ) ; printInorder ( node . right ) ; } public static void Main ( string [ ] args ) { GFG tree = new GFG ( ) ; int [ ] pre = new int [ ] { 10 , 30 , 20 , 5 , 15 } ; char [ ] preLN = new char [ ] { ' N ' , ' N ' , ' L ' , ' L ' , ' L ' } ; int n = pre . Length ; Node mynode = tree . constructTree ( pre , preLN , n , tree . root ) ; Console . WriteLine ( " Following ▁ is ▁ Inorder ▁ Traversal ▁ of ▁ the " + " Constructed ▁ Binary ▁ Tree : ▁ " ) ; tree . printInorder ( mynode ) ; } }