Abstract / Summary

Given preorder and postorder traversals of a binary tree with unique values, create the original tree.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 78% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Tree
• Divide And Conquer
• Hash Table
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation reconstructs a binary tree from its preorder and postorder traversal sequences. It relies on the invariant that the first element of the preorder list is always the current root, while the postorder list indicates when a subtree has been completely processed. By advancing two shared indices, the algorithm builds the tree in a single recursive pass without creating intermediate sub-arrays.

Key Steps

The algorithm begins by establishing two integer pointers that track the current position in each traversal list.

pre  = 0
post = 0

A nested helper function, deeper, carries out the recursive construction. The function is declared inside constructFromPrePost so it can capture and modify the outer pre and post variables via the nonlocal statement.

def deeper():
    nonlocal pre, post

The first action inside deeper is to create a new tree node using the element at the current preorder index. This node represents the root of the (sub)tree being built, and the preorder pointer is advanced immediately.

root = TreeNode(preorder[pre])
pre += 1

The left child is constructed only when the value of the newly created root does not match the current element in the postorder list. This condition signals that the left subtree has not yet been closed in the postorder sequence.

if root.val != postorder[post]:
    root.left = deeper()

After attempting to build the left subtree, the same check is performed again to decide whether a right subtree exists. If the root value still differs from the current postorder element, the algorithm recurses to build the right child.

if root.val != postorder[post]:
    root.right = deeper()

When both children (if any) have been processed, the postorder pointer is moved forward to mark the completion of the current root’s subtree, and the constructed node is returned to the caller.

post += 1
return root

Finally, the outer method invokes deeper once to start the construction and returns the fully assembled tree.

return deeper()

Edge Cases Handled

When a node is a leaf, the value of the root equals the current postorder element right after its creation. Both conditional blocks are skipped, the postorder index is incremented, and the leaf node is returned. This correctly terminates recursion for terminal nodes.

If a node has only a left child, the first conditional succeeds, building the left subtree, while the second conditional fails because the postorder pointer now points to the parent’s value. The algorithm therefore creates a left-only branch without attempting an unnecessary right recursion.

Conversely, when a node has only a right child, the left conditional fails (the left subtree is empty), but the second conditional succeeds, constructing the right subtree. The postorder pointer is still advanced only after the right subtree finishes, preserving the correct ordering.

The shared indices guarantee that the algorithm never reads beyond the bounds of the input lists, because each recursive call consumes exactly one preorder element and one postorder element when the corresponding subtree is closed.

Performance Optimizations

The implementation avoids the overhead of slicing the input lists for each recursive call. By using integer indices (pre and post) that are updated in place, the algorithm works directly on the original arrays, eliminating the need for additional memory allocation and reducing the number of Python object creations.

The nonlocal declaration allows the recursive helper to modify the outer index variables without passing them as arguments. This design keeps the function signature minimal and avoids the cost of repeatedly constructing argument tuples for each recursion level.

The early exit condition (root.val != postorder[post]) prevents unnecessary recursive calls. When the root value matches the current postorder element, the algorithm knows that the subtree is complete and skips further descent, thereby reducing the total number of function invocations.

Overall, the code achieves an efficient reconstruction by leveraging index tracking, in-place state mutation, and conditional recursion to minimize both time spent in Python-level operations and auxiliary memory usage.

Imagine you have a big box of numbered blocks that you want to put together into a tall tree shape. To build this tree, you have two special lists of instructions that tell you which number goes where.

The first list is called preorder, which tells you the order of the blocks starting from the very top piece and working down. The second list is called postorder, which shows the order of the blocks if you finish the bottom parts before moving up to the branches.

When this code starts, it looks at the first number in the preorder list to create the main top piece of the tree. Then, it uses the other list to figure out if there are more blocks to add to the left side or the right side.

The part called deeper is a little helper that keeps doing the same thing over and over. It picks up the next block from the pile, creates a branch, and then checks the postorder list to see if it has finished that part of the tree. If the number does not match what the postorder list expects to see next, the helper knows it needs to create a new branch underneath.

It keeps building and building until every single number from the lists has a spot in the tree. Once all the blocks are placed, the tree is finished and looks just like the one planned by the instructions.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java				Python			TS
	WalkCCC	C++		Java				Python
	leetcode.ca	C++		Java				Python		Go	TS
	LeetcodeHelp	C++		Java				Python
	Progiez	C++		Java				Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem						Ruby
	fengvyi	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007							Python
	lzl124631x	C++
	ruoru					Rust
	Shamik07								Dart
	suxrobGM				C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality