106. Construct Binary Tree from Inorder and Postorder Traversal

Description

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

inorder = [9, 3, 15, 20, 7]

postorder = [9, 15, 7, 20, 3]

Output: [3, 9, 20, null, null, 15, 7]

Solutions

TreeNode

// 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;
    }
}

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    private int postorderIndex = 0;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postorderIndex = postorder.length-1;
        return buildTree(inorder, postorder, 0, postorderIndex);
    }
    
    private TreeNode buildTree(int[] in, int[] post, int start, int end) {
        if(start > end) return null;
        
        TreeNode node = new TreeNode(post[postorderIndex--]);
        
        if(start == end) return node;
        
        int rootIndex = findRootIndex(in, start, end, node.val);
        
        node.right = buildTree(in, post, rootIndex+1, end);
        
        node.left = buildTree(in, post, start, rootIndex-1);
        
        return node;
    }
    
    private int findRootIndex(int[] in, int start, int end, int val) {
        while(start <= end) {
            if(in[start] == val) break;
            start++;
        }
        return start;
    }
}

Follow up

• Construct a Binary Search Tree from given postorder - GFG