Solution For Construct Binary Tree From Inorder And Postorder Traversal

Problem Statement:

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

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

Example:

Inorder traversal: [9,3,15,20,7] Postorder traversal: [9,15,7,20,3]

Return the following binary tree:

  3
 / \
9  20
  /  \
 15   7

Solution Approach:

Inorder traversal follows the left, root, right sequence whereas postorder follows the left, right, root sequence. From the postorder, we can find the root of the tree and then use that to divide the inorder array into left and right subtrees.

We can create a recursive function that takes in the two arrays and builds the tree recursively. The function can start by finding the root from the postorder array and then searching for the root in the inorder array. All elements to the left of the root in the inorder array can be used to build the left subtree and all elements to the right of the root in the inorder array can be used to build the right subtree.

Once the left and right subtrees are built, they can be attached to the root to create the final binary tree. The function can be recursively called with the left and right subtrees to build the complete binary tree.

Solution:

Here’s the Python solution for the problem:

“`
class TreeNode:
def init(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder or not postorder:
return None

    root_val = postorder.pop()
    root = TreeNode(root_val)

    idx = inorder.index(root_val)

    root.right = self.buildTree(inorder[idx+1:], postorder)
    root.left = self.buildTree(inorder[:idx], postorder)

    return root

“`

The above solution has a time complexity of O(n^2) since the index method used on lists with multiple same values takes O(n) time. We can improve the performance by using a hash map to store the index of each element in the inorder array, thus reducing the time complexity to O(n).

Here’s the optimized Python solution:

“`
class TreeNode:
def init(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
inorder_map = {}
for i, val in enumerate(inorder):
inorder_map[val] = i

    def helper(inorder, postorder, in_start, in_end, post_start, post_end):
        if in_start > in_end or post_start > post_end:
            return None

        root_val = postorder[post_end]
        root = TreeNode(root_val)

        idx = inorder_map[root_val]
        left_size = idx - in_start

        root.left = helper(inorder, postorder, in_start, idx-1, post_start, post_start+left_size-1)
        root.right = helper(inorder, postorder, idx+1, in_end, post_start+left_size, post_end-1)

        return root

    return helper(inorder, postorder, 0, len(inorder)-1, 0, len(postorder)-1)

“`
The above solution has a time complexity of O(n) and a space complexity of O(n).

Step by Step Implementation For Construct Binary Tree From 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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //edge case
        if(inorder.length == 0 || postorder.length == 0)
            return null;
        
        //build a hashmap of the inorder array to get the index of each value
        HashMap map = new HashMap();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        
        //call the helper function
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map);
    }
    
    public TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, HashMap map){
        //base case
        if(inStart > inEnd || postStart > postEnd)
            return null;
        
        //get the root from the postorder array
        int rootValue = postorder[postEnd];
        TreeNode root = new TreeNode(rootValue);
        
        //get the index of the root from the inorder array
        int rootIndex = map.get(rootValue);
        
        //calculate the number of elements in the left and right subtrees
        int leftTreeSize = rootIndex - inStart;
        int rightTreeSize = inEnd - rootIndex;
        
        //recursively build the left and right subtrees
        root.left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1, map);
        root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postEnd - rightTreeSize, postEnd - 1, map);
        
        return root;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # Base case: inorder and postorder are both empty
        if not inorder and not postorder:
            return None
        
        # Base case: only one element in inorder list
        if len(inorder) == 1:
            return TreeNode(inorder[0])
        
        # Find the root of the tree (last element of postorder list)
        root = TreeNode(postorder[-1])
        
        # Find the index of the root in the inorder list
        root_index = inorder.index(postorder[-1])
        
        # Slice the inorder and postorder lists around the root to get the left and right subtrees
        inorder_left = inorder[:root_index]
        inorder_right = inorder[root_index+1:]
        postorder_left = postorder[:root_index]
        postorder_right = postorder[root_index:-1]
        
        # Recursively build the left and right subtrees
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)
        
        return root

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
 
 //Given the inorder and postorder traversal of a binary tree, construct the binary tree.
 
 //Note:
 //You may assume that duplicates do not exist in the tree.
 
 //For example, given
 
 //inorder = [9,3,15,20,7]
 //postorder = [9,15,7,20,3]
 //Return the following binary tree:
 
    //    3
    //   / \
    //  9  20
    //    /  \
    //   15   7

var buildTree = function(inorder, postorder) {
    if (!inorder.length || !postorder.length) return null;
    
    let val = postorder.pop();
    let root = new TreeNode(val);
    
    let index = inorder.indexOf(val);
    
    root.right = buildTree(inorder.slice(index + 1), postorder.slice(index));
    root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index));
    
    return root;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        // Base case
        if (inorder.size() == 0 || postorder.size() == 0) {
            return NULL;
        }
        
        // Create a hashmap of the inorder traversal
        unordered_map inorderMap;
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        
        // Helper function
        return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderMap);
    }
    
    TreeNode* buildTreeHelper(vector& inorder, int inStart, int inEnd, vector& postorder, int postStart, int postEnd, unordered_map& inorderMap) {
        // Base case
        if (inStart > inEnd || postStart > postEnd) {
            return NULL;
        }
        
        // Get the root node from the postorder traversal and create the root
        int rootVal = postorder[postEnd];
        TreeNode* root = new TreeNode(rootVal);
        
        // Get the index of the root node in the inorder traversal
        int rootIndex = inorderMap[rootVal];
        
        // Recursively build the left and right subtrees
        int leftInStart = inStart;
        int leftInEnd = rootIndex - 1;
        int leftPostStart = postStart;
        int leftPostEnd = leftPostStart + leftInEnd - leftInStart;
        int rightInStart = rootIndex + 1;
        int rightInEnd = inEnd;
        int rightPostStart = leftPostEnd + 1;
        int rightPostEnd = postEnd - 1;
        
        root->left = buildTreeHelper(inorder, leftInStart, leftInEnd, postorder, leftPostStart, leftPostEnd, inorderMap);
        root->right = buildTreeHelper(inorder, rightInStart, rightInEnd, postorder, rightPostStart, rightPostEnd, inorderMap);
        
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        //Check for invalid inputs
        if(inorder == null || postorder == null || inorder.Length != postorder.Length)
        {
            return null;
        }
        
        return BuildTreeHelper(inorder, postorder, 0, inorder.Length - 1, 0, postorder.Length - 1);
    }
    
    private TreeNode BuildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd)
    {
        //Base case - reached the end of the traversals
        if(inStart > inEnd || postStart > postEnd)
        {
            return null;
        }
        
        //Create the root node with the last element in the postorder traversal
        TreeNode root = new TreeNode(postorder[postEnd]);
        
        //Find the index of the root node in the inorder traversal
        int rootIndex = Array.IndexOf(inorder, root.val);
        
        //Use the index to calculate the number of nodes in the left and right subtrees
        int leftTreeSize = rootIndex - inStart;
        int rightTreeSize = inEnd - rootIndex;
        
        //Recursively build the left and right subtrees
        root.left = BuildTreeHelper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftTreeSize - 1);
        root.right = BuildTreeHelper(inorder, postorder, rootIndex + 1, inEnd, postStart + leftTreeSize, postEnd - 1);
        
        return root;
    }
}