Construct Binary Tree from PreOrder , InOrder and PostOrder traversals.

Smrita Pokharel

·

Follow

2 min read

·

Apr 12, 2021

--

Listen

Share

1. Preorder and Inorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    Map<Integer, Integer> map = new HashMap<>();
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(0,0,inorder.length-1,preorder,inorder);
    }
    
    public TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preOrder, int[] inOrder){
        
        if(preStart>preOrder.length-1 || inStart > inEnd){
            return null;
        }
        
        int inIndex = map.get(preOrder[preStart]);
        
        TreeNode root = new TreeNode(preOrder[preStart]);
        
        root.left = buildTree(preStart+1,inStart, inIndex-1, preOrder,inOrder);
        root.right = buildTree(preStart+inIndex-inStart+1, inIndex+1, inEnd, preOrder, inOrder);
        
        return root;
    }
}

2. Inorder and Postorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        
        return construct(postorder.length-1,0,inorder.length-1,inorder,postorder);
    }
    
    public TreeNode construct(int postEnd, int inStart, int inEnd, int[] inorder, int[] postorder){
        
        if(postEnd<0 || inStart>inEnd){
            return null;
        }
        
        TreeNode root = new TreeNode(postorder[postEnd]);
        
        int inIndex = map.get(root.val);
        
        root.left = construct(postEnd-(inEnd-inIndex)-1,inStart,inIndex-1,inorder,postorder);
        root.right = construct(postEnd-1, inIndex+1, inEnd, inorder,postorder);
        
        return root;
    }
}