Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement:-

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.

Link: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

Problem Explanation with examples:-

Example 1

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Explanation: Given the following tree...
  3
 / \
9  20
  /  \
 15   7
...Return the following tree...

Example 2

Input: inorder = [-1], postorder = [-1]
Output: [-1]
Explanation: Given the following tree in inorder traversal and postorder traversal
 -1
...Return the following tree...

Constraints

• 1 <= inorder.length <= 3000

• postorder.length == inorder.length

• -3000 <= inorder[i], postorder[i] <= 3000

• inorder and postorder consist of unique values.

• Each value of postorder also appears in inorder.

• inorder is guaranteed to be the inorder traversal of the tree.

• postorder is guaranteed to be the postorder traversal of the tree.

Intuition:-

• A binary tree problem again so recursion is obvious.

• Inorder traversal gives us the left subtree, root, and right subtree.

• Postorder traversal gives us the left subtree, right subtree, and root.

• So we can use the last element of postorder as the root.

• Then we can find the root in the inorder traversal.

• Then we can split the inorder array into left subtree and right subtree from the root.

• Keep doing this recursively until we reach the leaf nodes.

Solution:-

• Check if inorder is empty, if so return None.

• Pop the last element of postorder and put it in rootVal.

• Create a TreeNode with rootVal.

• Find the index of rootVal in inorder.

• Recursively call buildTree on the right subtree of inorder and postorder, and also slice the inorder array from the root index + 1 to the end.

• Recursively call buildTree on the left subtree of inorder and postorder, and also slice the inorder array from the start to the root index.

• Return root.

Code:-

JAVA Solution

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        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) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        int inOrderIdx = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inOrderIdx = i;
                break;
            }
        }

        int leftSubTreeSize = inOrderIdx - inStart;
        root.left = buildTreeHelper(inorder, postorder, inStart, inOrderIdx - 1, postStart, postStart + leftSubTreeSize - 1);
        root.right = buildTreeHelper(inorder, postorder, inOrderIdx + 1, inEnd, postStart + leftSubTreeSize, postEnd - 1);

        return root;
    }
}

Python Solution

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

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

        inOrder_idx = inorder.index(rootVal)

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

        return root

Complexity Analysis:-

TIME:-

Time complexity of the buildTree function is O(n^2) in the worst-case scenario, where n is the number of elements in the inorder and postorder traversals. This happens when the input binary tree is skewed, and each node has only one child. In such a case, the inorder.index method takes O(n) time to find the index of the root node, and this operation is performed for each node of the tree. The pop method also takes O(1) time. Therefore, the overall time complexity is O(n^2).

However, in the best-case scenario, the binary tree is balanced, and each node has two children. In this case, the inorder.index method is only called once for each node, and the pop method is called exactly n times. Therefore, the time complexity is O(n).

SPACE:-

Space complexity of the buildTree function is O(n) in the worst-case scenario. This happens when the input binary tree is skewed, and the recursive function calls accumulate on the call stack. In the best-case scenario, the binary tree is balanced, and the height of the call stack is logarithmic to the number of elements in the tree, resulting in a space complexity of O(log n).

References:-

• Recursion

• Binary Tree

• Tree Traversals

Connect with me:-

• Twitter

• Github

• LinkedIn