889. Construct Binary Tree From Preorder And Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal

A binary tree is one of the most fundamental data structures in computer science, serving as a backbone for countless algorithms and applications—from expression parsing to decision-making systems. When given two sequential representations of a tree—the preorder traversal and the postorder traversal—one can reconstruct the exact binary tree structure. This technique is particularly valuable because both traversals visit each node exactly once, making them efficient ways to encode hierarchical relationships. In this guide, we explore how to construct a binary tree from preorder and postorder traversals, break down the underlying logic, and walk through practical implementation details that will help you master this essential algorithmic skill.

Introduction

The problem of constructing a binary tree from its preorder and postorder traversals appears frequently in coding interviews and competitive programming challenges. Unlike reconstruction from just one traversal, which would leave ambiguity—for example, knowing only preorder cannot distinguish between left and right subtrees—it becomes straightforward when both views are available. What makes this task interesting is that while preorder traversal visits nodes in the order Root → Left → Right, and postorder visits them as Left → Right → Root, these two sequences alone are sufficient to uniquely determine a binary tree (provided certain conditions are met). This dual representation essentially captures the tree's structure twice, allowing us to reverse-engineer the hierarchy and rebuild the original tree efficiently Small thing, real impact..

This is where a lot of people lose the thread Simple, but easy to overlook..

Understanding this transformation requires familiarity with both traversal types. Conversely, a postorder traversal records the children before visiting the parent itself. A preorder traversal records the root node first, followed by traversing the left subtree recursively, then the right subtree. By analyzing how these patterns intersect across different branches of the tree, we can deduce parent-child relationships and piece together the full structure.

Understanding Preorder and Postorder Traversals

Before diving into the reconstruction algorithm, let's establish a solid foundation with these two traversal methods. Both are depth-first approaches that visit each node exactly once, though they differ in the sequence they encounter nodes Practical, not theoretical..

Preorder Traversal follows the pattern: Root → Left Subtree → Right Subtree. To give you an idea, if our tree has root A, left child B, and right child C, the preorder sequence would be A, B, C. This order proves invaluable because it immediately reveals where the root sits within the overall structure.

Postorder Traversal follows: Left Subtree → Right Subtree → Root. Using the same example, the postorder sequence would be B, C, A. This is often critical during tree operations like deleting nodes or evaluating expressions, since all descendants appear before their parents That alone is useful..

Consider a concrete example to illustrate these concepts. Suppose we have a simple binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Its preorder traversal yields [1, 2, 4, 5, 3, 6] and its postorder traversal yields [4, 5, 2, 6, 3, 1]. Notice how the root (1) appears first in preorder and last in postorder—this symmetry is a key insight that enables reconstruction And that's really what it comes down to. Turns out it matters..

The Algorithm: Step-by-Step Reconstruction

Reconstructing a binary tree from preorder and postorder arrays involves identifying the root, determining subtree boundaries, and recursively building the left and right subtrees. Here's the systematic approach:

Step 1: Identify the Root Node

The first element in the preorder array is always the root of the current subtree. Consider this: since the root appears first in preorder and last in postorder, we can easily locate it. Once identified, we know this node becomes the root of whatever subtree we're processing.

Step 2: Find the Split Point Between Left and Right Subtrees

The crucial challenge lies in separating the left and right subtrees. That's why we know the size of each subtree implicitly from the traversals themselves. Specifically, the number of elements in the left part of the preorder array equals the length of the left subtree, which can be derived from the position of the root in the postorder array.

To find this split point:

• The root (first element in preorder) marks the beginning of the left subtree in postorder.
• All elements after the root until the corresponding index in postorder indicate the left subtree; everything after that belongs to the right subtree.

This changes depending on context. Keep that in mind.

More concretely, if pre is the preorder array and post is the postorder array, and root = pre[0], we search for root in post. Let its index be i. Then:

• The left subtree consists of elements from pre[1] up to pre[i-1]
• The right subtree consists of elements from pre[i] onwards

For our earlier example, root=1 appears at index 4 in postorder. Thus, the left subtree contains indices 1-3 ([2,4,5]) and the right subtree contains indices 5-5 ([3,6]).

Step 3: Recursively Build Left and Right Subtrees

Once we've partitioned the arrays correctly, we apply the same logic recursively to each subtree. Even so, the left subtree is constructed using the left portion of preorder and the corresponding left portion of postorder. Similarly, the right subtree uses the remaining portions. Base cases occur when either the preorder or postorder subarray is empty (returning null) Practical, not theoretical..

Step 4: Assemble the Tree Structure

At each recursive call, create a new tree node with the root value, attach the left and right children (which may be null), and return the completed subtree.

Working Through a Practical Example

Let's reconstruct a binary tree using this method. Consider the following preorder and postorder sequences:

Preorder: [3, 9, 20, 15, 7] Postorder: [9, 15, 7, 20, 3]

We'll build the tree step by step:

1. First iteration: The root is 3 (first element in preorder).
   • Search for 3 in postorder → found at index 4.
   • This means the left subtree has elements [9, 20, 15, 7] (indices 1-3) and the right subtree has [20] (index 5? Wait, let me recalculate).

Actually, let me correct my calculation. With pre=[3,9,20,15,7] and post=[9,15,7,20,3]:

• Root = pre[0] = 3
• Index of root