Construct a Perfect Binary Tree from Preorder Traversal | Java program for the above approach ; Structure of the tree ; Function to create a new node with the value val ; Return the newly created node ; Function to create the Perfect Binary Tree ; If preStart > preEnd return NULL ; Initialize root as pre [ preStart ] ; If the only node is left , then return node ; Parameters for further recursion ; Recursive Call to build the subtree of root node ; Return the created root ; Function to build Perfect Binary Tree ; Function to print the Inorder of the given Tree ; Base Case ; Left Recursive Call ; Print the data ; Right Recursive Call ; Driver Code ; Function Call ; Print Inorder Traversal
public class Main { static class Node { public int data ; public Node left , right ; public Node ( int val ) { data = val ; left = right = null ; } } static Node getNewNode ( int val ) { Node newNode = new Node ( val ) ; return newNode ; } static Node buildPerfectBT_helper ( int preStart , int preEnd , int [ ] pre ) { if ( preStart > preEnd ) return null ; Node root = getNewNode ( pre [ preStart ] ) ; if ( preStart == preEnd ) return root ; int leftPreStart = preStart + 1 ; int rightPreStart = leftPreStart + ( preEnd - leftPreStart + 1 ) / 2 ; int leftPreEnd = rightPreStart - 1 ; int rightPreEnd = preEnd ; root . left = buildPerfectBT_helper ( leftPreStart , leftPreEnd , pre ) ; root . right = buildPerfectBT_helper ( rightPreStart , rightPreEnd , pre ) ; return root ; } static Node buildPerfectBT ( int [ ] pre , int size ) { return buildPerfectBT_helper ( 0 , size - 1 , pre ) ; } static void printInorder ( Node root ) { if ( root == null ) return ; printInorder ( root . left ) ; System . out . print ( root . data + " ▁ " ) ; printInorder ( root . right ) ; } public static void main ( String [ ] args ) { int [ ] pre = { 1 , 2 , 4 , 5 , 3 , 6 , 7 } ; int N = pre . length ; Node root = buildPerfectBT ( pre , N ) ; System . out . print ( " Inorder ▁ traversal ▁ of ▁ the ▁ tree : ▁ " ) ; printInorder ( root ) ; } }