Posts Construct Binary Tree from Inorder and Postorder Traversal
Post
Cancel

Construct Binary Tree from Inorder and Postorder Traversal

PROBLEM DESCRIPTION

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildHelper(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
    }
    
    //ins -> inorder start
    //ine -> inorder end
    //ps -> postorder start
    //pe -> postorder end
    public TreeNode buildHelper(int[] inorder, int[] postorder, int ins, int ine, int ps, int pe){
        
        if(ins > ine || ps > pe) return null;

        //Last element in the postorder is the root
        int r = postorder[pe];
        TreeNode node = new TreeNode(r);

        //Get index of the root element in inorder
        int idx = getRootInOrder(inorder, r, ins, ine);

        //Size of right subtree
        int sizeOfRST = ine - idx;

        //We can now assign right of this node to subtree which can be constructed using recusive call
        node.right = buildHelper(inorder, postorder, idx+1, ine, pe-sizeOfRST, pe-1);
        node.left = buildHelper(inorder, postorder, ins, idx-1, ps, pe-sizeOfRST-1);
        
        return node;

    }

    public int getRootInOrder(int[] inorder, int r, int start, int end){
        for(int i=start; i<=end; i++){
            if(inorder[i] == r) return i;
        }
        return -1;
    }
    
}
This post is licensed under CC BY 4.0 by the author.