Construct Binary Tree from Preorder and Postorder Traversal

Updated on 08 May, 2025
Construct Binary Tree from Preorder and Postorder Traversal header image

Problem Statement

In this problem, we are given two arrays representing the preorder and postorder traversals of a binary tree. The task is to reconstruct the original binary tree from these traversal sequences. It is essential to note that the values in both arrays are unique and belong distinctly to the nodes of the tree. You can potentially construct multiple valid binary trees from the given sequences, but only one needs to be returned as an output.

Examples

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]

Example 2

Input:

preorder = [1], postorder = [1]

Output:

[1]

Constraints

  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • All the values of preorder are unique.
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • All the values of postorder are unique.
  • It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Approach and Intuition

The reconstruction of a binary tree from its preorder and postorder traversals hinges on understanding these traversals' properties and how they define the structure of the tree. The root of the problem absorbs the fact that preorder traversal starts with the root node followed by the subtrees, while postorder traversal ends with the root after covering the subtrees. Here’s a structured approach to solve the problem:

  1. Identify the root of the tree from the preorder array (it's always the first element).
  2. Locate the roots of the left and right subtrees. The root of the left subtree in preorder will directly follow the main root. Similarly, in postorder, the root before the main root is the root of the right subtree.
  3. Develop a recursive function that,
    • Takes corresponding sections of the preorder and postorder arrays that deal with a specific subtree.
    • Determines the roots and boundaries for the next level of recursion.
  4. Continue splitting the tree into subtrees recursively until the entire tree is reconstructed.
  5. If at any step, the corresponding subtrees' information contradicts (like non-alignment of array boundaries), you might need to revisit the slicing done based on roots found.

Example Elaborations from given examples:

  • Example 1: Starting with 1 as the root from preorder, we locate the next elements to build the subtrees. The tree is continuously spliced following the rules derived from the preorder and postorder traces until all elements are correctly placed.
  • Example 2: Being a single element array, the root is 1, and as there are no further elements, 1 itself is the entire tree.

The recursive military precision applied when building each subtree ensures every node is correctly placed, respecting their original relationships in the given tree, as reflected by its traversals.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    TreeNode* buildFromPrePost(vector<int>& pre, vector<int>& post) {
        int prePos = 0;
        int postPos = 0;
        return build(prePos, postPos, pre, post);
    }

private:
    TreeNode* build(int& prePos, int& postPos, vector<int>& pre, vector<int>& post) {
        TreeNode* node = new TreeNode(pre[prePos]);
        prePos++;
        
        if (node->val != post[postPos]) {
            node->left = build(prePos, postPos, pre, post);
        }

        if (node->val != post[postPos]) {
            node->right = build(prePos, postPos, pre, post);
        }
        
        postPos++;
        
        return node;
    }
};

The provided C++ solution describes the process of constructing a binary tree from its preorder and postorder traversal sequences. The buildFromPrePost function serves as the entry point and internally utilizes a helper function build for recursive tree construction.

Here's a breakdown of the approach:

  • Use two vectors pre and post representing the preorder and postorder traversal sequences of the binary tree, respectively.

  • Start by defining initial positions, prePos and postPos, to keep track of the current node in the construction process and initiate recursive tree building.

  • The helper function build performs the following:

    • First, create a new TreeNode with the current value from the preorder sequence.
    • Increment the prePos to move to the next element for subsequent recursive calls.
    • Check if the value at the current prePos does not match the corresponding value in post at postPos to decide if it should recursively create and attach the left child to the current node.
    • Similarly, recheck the condition to decide for the right child. This is essential as the second condition ensures the correct formation of the tree structure respecting both traversals.
    • Upon completion of children assignments, increment postPos to signify that the node and its children have been fully constructed according to the postorder sequence.

This logic efficiently reconstructs the binary tree uniquely determined by the given preorder and postorder lists, assuming no duplicated elements are present. The algorithm utilizes recursion anchored by traversal position tracking to progressively build each node and attach appropriate children until the traversals are fully represented in the tree structure.

java
class Solution {

    private int indexPre = 0;
    private int indexPost = 0;

    public TreeNode buildFromPreAndPost(int[] pre, int[] post) {
        return buildTree(pre, post);
    }

    private TreeNode buildTree(int[] pre, int[] post) {
        TreeNode node = new TreeNode(pre[indexPre++]);

        if (node.val != post[indexPost]) {
            node.left = buildTree(pre, post);
        }

        if (node.val != post[indexPost]) {
            node.right = buildTree(pre, post);
        }

        indexPost++;
        return node;
    }
}

In the provided Java solution, you construct a binary tree based on given preorder and postorder traversal arrays. The computation leverages a recursive approach for construction. Here's a concise summary of how this code works:

  • A TreeNode class needs to be available, which is not shown in the snippet but it generally contains the structure for a binary tree node (int val, TreeNode left, TreeNode right).

  • The class Solution contains:

    • Two private instance variables, indexPre and indexPost, initialized at 0. These act as pointers to keep track of the current indices in the preorder and postorder traversal arrays respectively.

    • The buildFromPreAndPost method as a public entry point which directly calls buildTree using the provided preorder and postorder traversal arrays.

    • The buildTree method creates nodes as it recursively parses the traversal arrays:

      • A new TreeNode is instantiated using the current value in preorder indexed by indexPre, which is then incremented.
      • As long as the value of the current node doesn’t match the value at the current postorder index, the left child is recursively populated.
      • The same process checks and assigns the right child (if the values still do not match).
      • After setting potential left and right children, indexPost is incremented.
  • The tree construction ends when all elements from the preorder and postorder traversal arrays are used up, ensuring the indices indexPre and indexPost facilitate correct placement of nodes based on both ordering constraints.

With this structure, ensure the implementation of the TreeNode class aligns with this logic, and the approach will correctly build the binary tree from the preorder and postorder traversals. This method balances efficient tree construction while correctly adhering to the constraints intrinsic to the specified tree traversals.

python
class Solution:
    def __init__(self):
        self.preorder_index = 0
        self.postorder_index = 0

    # Helper function to recursively construct the binary tree
    def buildTreeFromPrePost(
        self, preorder: List[int], postorder: List[int]
    ) -> Optional[TreeNode]:
        return self._build_tree(preorder, postorder)

    def _build_tree(
        self, preorder: List[int], postorder: List[int]
    ) -> Optional[TreeNode]:
        node = TreeNode(preorder[self.preorder_index])
        self.preorder_index += 1

        # Recursively build the left subtree unless the current root is 
        # at the end of its subtree in postorder list
        if node.val != postorder[self.postorder_index]:
            node.left = self._build_tree(preorder, postorder)

        # Recursively build the right subtree unless the current root is 
        # at the end of its subtree in postorder list.
        if node.val != postorder[self.postorder_index]:
            node.right = self._build_tree(preorder, postorder)

        # Indicate this node and its subtree are fully constructed
        self.postorder_index += 1
        return node

You can construct a binary tree from preorder and postorder traversal using Python3 by implementing a recursive strategy. Begin by initializing class variables to track the indexes during traversal, then use these indexes to build the tree node by node.

  • Define a main function buildTreeFromPrePost that begins the recursive construction.

  • Implement the recursive helper functionality _build_tree which:

    1. Creates the current tree node from the preorder list using the current index.
    2. Increment the preorder index.
    3. Recursively constructs the left subtree if the current node value does not match the current postorder value.
    4. Recursively constructs the right subtree under the same condition.
    5. After constructing left and right subtrees, increments the postorder index to move to the next subtree root.
    6. Returns the constructed node, which will recursively build up to the complete tree.

This approach effectively leverages the properties of tree traversals: preorder for root identification and postorder for children completion checks, iterating until the entire tree is reconstructed. Each recursive call handles a node construction, and the tree grows as the stack unwinds, piecing together left and right children.

Comments

No comments yet.