Introduction

For a general binary tree, one traversal is not enough to reconstruct the tree uniquely. But for a binary search tree with unique keys, the answer is different: a single preorder traversal or a single postorder traversal is enough to reconstruct the BST. The BST ordering rule carries extra structure, so you do not need the same amount of information that a general binary tree requires.

Why a BST Is Special

A BST has the property that:

• every value in the left subtree is smaller than the root
• every value in the right subtree is larger than the root

That ordering constraint dramatically reduces ambiguity.

For an arbitrary binary tree, preorder alone does not tell you where the left subtree ends and the right subtree begins. In a BST, the value ranges determine those boundaries.

One Preorder Traversal Is Enough

Suppose the preorder traversal is:

10 5 1 7 40 50

The first value, 10, is the root. In a BST preorder sequence, values less than 10 belong to the left subtree and values greater than 10 belong to the right subtree.

So:

• left subtree preorder: 5 1 7
• right subtree preorder: 40 50

You can then recurse on each side.

Example Construction From Preorder

A simple Python implementation uses range bounds.

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.left = None
5        self.right = None
6
7
8def build_bst_from_preorder(preorder):
9    index = 0
10
11    def helper(lower, upper):
12        nonlocal index
13        if index == len(preorder):
14            return None
15
16        value = preorder[index]
17        if value < lower or value > upper:
18            return None
19
20        index += 1
21        node = Node(value)
22        node.left = helper(lower, value)
23        node.right = helper(value, upper)
24        return node
25
26    return helper(float("-inf"), float("inf"))

This works because every recursive call knows the legal value range for that subtree.

One Postorder Traversal Is Also Enough

The same idea works with postorder if you process the sequence from the end. In postorder, the last element is the root, and the BST bounds again tell you how to split the remaining values.

So for unique keys:

• preorder alone is sufficient
• postorder alone is sufficient

Inorder alone is not sufficient, because the inorder traversal of a BST is just the sorted key list. Many different BST shapes can produce the same sorted order.

What About Two Traversals?

If someone learned that you need inorder plus preorder or inorder plus postorder to reconstruct a tree, that statement applies to general binary trees. It is true there, but it is stronger than necessary for a BST.

That is the key distinction:

• general binary tree: usually need two traversals, one of them inorder
• BST with unique keys: one preorder or one postorder traversal is enough

Common Pitfalls

• Applying the rule for general binary trees directly to BSTs.
• Thinking inorder alone is enough because BST inorder is sorted.
• Forgetting that uniqueness of keys matters for unambiguous reconstruction.
• Missing the fact that preorder and postorder work because BST ordering supplies subtree boundaries.
• Assuming level-order is required when preorder already contains enough information.

Summary

• For a BST with unique keys, one preorder traversal is enough to reconstruct it.
• One postorder traversal is also enough.
• Inorder alone is not enough because it only gives sorted values.
• The BST ordering property provides structural information that general binary trees do not have.
• The "two traversals required" rule applies to general binary trees, not specifically to BSTs.