MediumArrayHash TableDivide and ConquerTreeBinary Tree

Construct Binary Tree from Inorder and Postorder Traversal

1 approach, code in every language

You are given two integer arrays, inorder and postorder. The inorder array records the node values of a binary tree during an inorder traversal (left, root, right), and postorder records them during a postorder traversal (left, right, root).

All values are distinct. Build the binary tree that produces these two traversals and return its root.

Example 1

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

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

3 is the root because it comes last in postorder. It sits at index 1 in inorder, so [9] is the left subtree and [15,20,7] is the right subtree.

Example 2

Input: inorder = [-1], postorder = [-1]

Output: [-1]

Only one node exists, so the tree is a single root.

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.

Recursion with an Inorder Index Map

Take the last postorder value as the root, split inorder around it, and build the right subtree before the left while consuming postorder from the back.

Loading animation…

Intuition

Postorder visits the root last, so the final unused postorder value is the root of the current subtree. Just as with the preorder/inorder pairing, the root's position in inorder separates the left subtree from the right subtree. Because we consume postorder from its end and postorder lists the right subtree immediately before the root, we must build the right subtree before the left one. A hash map from value to inorder index gives O(1) root positioning, and a single backward-moving postorder pointer hands out roots in the correct order.

Algorithm walkthrough

1Map every inorder value to its index and set a postorder pointer at the last position.
2Define a recursive helper that takes the inorder bounds [left, right] of the current subtree.
3Return null when left is greater than right.
4Read the value at the postorder pointer as the root and decrement the pointer, then find its inorder index mid.
5Build the right subtree from [mid + 1, right] first, then the left subtree from [left, mid - 1], mirroring the reverse consumption of postorder.
6Return the root; start the recursion over the full inorder range.

Implementation

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(inorder)}
        self.post = len(postorder) - 1

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            root_val = postorder[self.post]
            self.post -= 1
            root = TreeNode(root_val)
            mid = idx[root_val]
            root.right = build(mid + 1, right)
            root.left = build(left, mid - 1)
            return root

        return build(0, len(inorder) - 1)

Time

O(n)

Space

O(n)

Every node is built once with O(1) inorder lookups. Space covers the index map and the recursion stack, up to O(n) for a degenerate tree.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Rebuilding a Rig From Two Readings is our own problem on the technique behind Construct Binary Tree from Inorder and Postorder Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free