MediumArrayHash TableDivide and ConquerTreeBinary Tree

Construct Binary Tree from Preorder and Postorder Traversal

1 approach, code in every language

You are given two integer arrays, preorder and postorder, that describe a binary tree with distinct node values. preorder gives the values in preorder traversal order (root, left, right) and postorder gives them in postorder order (left, right, root).

Reconstruct any binary tree whose preorder traversal equals preorder and whose postorder traversal equals postorder. If more than one tree is possible you may return any of them, and it is guaranteed that at least one valid answer exists.

Example 1

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]

1 is the root. 2, the next preorder value, roots the left subtree; it appears at index 2 in postorder, so [4,5,2] is the left block and [6,7,3] is the right block.

Example 2

Input: preorder = [1], postorder = [1]

Output: [1]

A single node is returned as the root.

Constraints

1 <= preorder.length <= 30
preorder.length == postorder.length
1 <= preorder[i], postorder[i] <= preorder.length
preorder and postorder consist of distinct values.
Both preorder and postorder are valid traversals of the same binary tree.

Recursion with a Postorder Index Map

Use preorder[0] as the root and preorder[1] as the left child's root; locate that left root in postorder to size the left subtree, then partition both sequences.

Loading animation…

Intuition

In preorder the root comes first and is immediately followed by the entire left subtree, so preorder's second unused value is the root of the left subtree whenever one exists. In postorder the left subtree appears as a contiguous block that ends exactly where that left-subtree root sits, so finding that value in postorder tells us how large the left subtree is. With the left size known, the remaining values split cleanly into the right subtree. Because the two traversals can describe more than one tree, we consistently treat the second preorder value as a left child, which yields one valid answer. A postorder index map plus a forward-moving preorder pointer keeps every step O(1).

Algorithm walkthrough

1Map each postorder value to its index and set a preorder pointer at 0.
2Define a helper that works over the postorder bounds [left, right] of the current subtree.
3Return null if left exceeds right; otherwise create the root from the current preorder value and advance the pointer.
4If left equals right the subtree is a single leaf, so return it immediately.
5Look up the next preorder value in postorder to get mid, the last index of the left subtree, then build the left subtree from [left, mid] and the right subtree from [mid + 1, right - 1].
6Return the root; the initial call covers the entire postorder range.

Implementation

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(postorder)}
        self.pre = 0

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

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

Time

O(n)

Space

O(n)

Each node is produced once, and locating the left-subtree root in postorder is O(1) through the index map. Space is the index map plus recursion stack, up to O(n).

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 The Inspection Rig is our own problem on the technique behind Construct Binary Tree from Preorder 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