Reconstruct the tree by given various traversals.

In the previous section, we explained how to produce the four types of tree traversals—LevelOrder, PreOrder, PostOrder, and InOrder—for a given tree. Now, let us reverse the problem: if we are given one or more traversals of an existing tree, can we reconstruct that tree and also derive its other traversals? The answer is typically yes. Next, we will examine several scenarios, including cases where reconstruction is possible and cases where it is not.

Note

In this chapter, all discussions refer to Binary Trees or Binary Search Trees. Also, every node's key/value in the tree is distinct

---

Single Traversal: Not Enough to Determine a Tree

First, consider the case where only one traversal is given:

• LevelOrder: If the number of elements is exactly 1, 3, 7, 15, and so on (i.e., 2^h+1^- 1), then the tree must be a perfect tree, making it possible to reconstruct. Otherwise, we cannot decide how to fill any partially empty level.

• PostOrder, InOrder, or PreOrder alone do not suffice. For instance, multiple different trees can share the same single traversal sequence.

• For PostOrder：

     (1)                 (1)
    /   \                   \
  (3)   (2)                  (2)
                               \
                                (3)

• For PreOrder:

     (1)                (1)     
        \              /   \
         (2)         (2)   (3)
           \
            (3)

• For InOrder

     (1)                (2)     
        \              /   \
         (2)         (1)   (3)
           \
            (3)

Clearly, for a single given traversal, we can usually find different tree structures that produce the same traversal sequence.

---

When Two Traversals Fail to Determine a Tree

Cases Where Two Given Traversals Fail to Determine the Tree Structure (Excluding Level-Order):

• Given two traversals—PreOrder (root → left subtree → right subtree) and Post-Order (left subtree → right subtree → root)—we can identify the root node from the first element of Pre-Order and the last element of Post-Order. However, we cannot perfectly determine how the left and right subtrees are distributed, which can lead to different tree shapes yielding the same pair of traversals.

---

Two Traversals That Uniquely Determine a Tree

Finally, let’s discuss the scenarios in which two given traversals can precisely determine a tree’s structure.

The given traversals must be Post-Order + InOrder or Pre-Order + In-Order.

Tip

This article focuses on one such scenario; the other(Pre-Order) follows a similar logic, try to deduce the pattern yourself!

• We will focus on Post-Order + In-Order here

• Key Insight: The last node in postorder is always the root. In inorder, all nodes to the left of the root belong to the left subtree, and all to the right belong to the right subtree.

• Recursive Idea:

1. Identify the root from postorder’s last element.
2. Find that root in inorder. Everything to the left is the left subtree, and everything to the right is the right subtree.
3. Determine which parts of postorder correspond to these subtrees.
4. Recursively repeat this partitioning for left and right subtrees.

Because each subtree division is unique when node values are distinct, the original tree is reconstructed unambiguously.

One Example

Given Traversal:

PreOrder: 3 1 2 10 5 4 12

InOrder: 2 1 3 4 5 10 12

As we can see, this tree isn't a Binary Search Tree, since the Inorder is not in increasing order.

Detail Steps:

Firstly, treat the first element3 in the PreOrder Traversal as the Root Node(the PreOrder Traversal starts from the root node then left subtree then right subtree then recursively repeat)

Then find where is the 3 in InOrder Traversal:

InOrder: 2 1 [3] 4 5 10 12

OK, remind that if we found the root in the InOrder traversal, we can divide the tree and determine its left subtree and right subtree(InOrder Traversal starts from left subtree, then root node, then right subtree).

Left Subtree: 2 1

Right Subtree: 4 5 10 12

Then we move back to the PreOrder Traversal, recursively repeat this step:

• Left Subtree in PreOrder: 1 2, so first element is 1 now, so the root of left subtree is 1, does it (1) have left subtree and left subtree? Check the InOrder to determine it: the left subtree in InOrder: 1 2, there is some element(2) on the right hand side of 1 but nothing on the left side! It shows that no element exists on the left subtree of 1, now we should construct a tree like this

          (3)
         /   
       (1)
         \

Note

I recommend to draw the edge of the current node you visit, then you will see clearly whether it has a child and which child or not.

Then the left tree only have a 2 left, and clearly it should be on the position of 1's right child.

          (3)
         /   
       (1)
         \
         (2)

Now our root and all the left subtree of the root is done.

After this, repeat the steps mentioned above and recursively finish the right subtree.

Final tree:

          (3)
      /         \
   (1)           (10)
      \         /    \
      (2)     (5)    (12)
              /
            (4)

---

Practice!

Given the following Post-Order traversal of a binary search tree:

Post-Order: A D B L N G Y W T

find the Pre-Order and Level-Order traversals

For reference, the English alphabet will be ordered with the following relative values:

A < B < C < D < E < F < G < H < I < J < K < L < M < N < O < P < Q < R < S < T < U < V < W < X < Y < Z

Click to see the Answer!

PreOrder: T G B A D N L W Y

Level-Order: T G W B N Y A D L

Welcome any questions or further discussion on this topic.