Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

889. Construct Binary Tree from Preorder and Postorder Traversal - Leetcode Solution

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, preorder, postorder):
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        if len(preorder) == 1:
            return root
        # Find the left subtree root in postorder
        left_root_val = preorder[1]
        left_subtree_size = postorder.index(left_root_val) + 1
        root.left = self.constructFromPrePost(preorder[1:left_subtree_size+1], postorder[:left_subtree_size])
        root.right = self.constructFromPrePost(preorder[left_subtree_size+1:], postorder[left_subtree_size:-1])
        return root
      
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector& preorder, vector& postorder) {
        if (preorder.empty()) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        if (preorder.size() == 1) return root;
        int left_root_val = preorder[1];
        int left_subtree_size = 0;
        for (int i = 0; i < postorder.size(); ++i) {
            if (postorder[i] == left_root_val) {
                left_subtree_size = i + 1;
                break;
            }
        }
        root->left = constructFromPrePost(
            vector(preorder.begin() + 1, preorder.begin() + 1 + left_subtree_size),
            vector(postorder.begin(), postorder.begin() + left_subtree_size)
        );
        root->right = constructFromPrePost(
            vector(preorder.begin() + 1 + left_subtree_size, preorder.end()),
            vector(postorder.begin() + left_subtree_size, postorder.end() - 1)
        );
        return root;
    }
};
      
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }
    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        if (preStart == preEnd) return root;
        int leftRootVal = preorder[preStart + 1];
        int leftIndex = postStart;
        while (postorder[leftIndex] != leftRootVal) leftIndex++;
        int leftSize = leftIndex - postStart + 1;
        root.left = build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, leftIndex);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, postorder, leftIndex + 1, postEnd - 1);
        return root;
    }
}
      
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function(preorder, postorder) {
    if (preorder.length === 0) return null;
    const root = new TreeNode(preorder[0]);
    if (preorder.length === 1) return root;
    const leftRootVal = preorder[1];
    const leftSubtreeSize = postorder.indexOf(leftRootVal) + 1;
    root.left = constructFromPrePost(preorder.slice(1, leftSubtreeSize + 1), postorder.slice(0, leftSubtreeSize));
    root.right = constructFromPrePost(preorder.slice(leftSubtreeSize + 1), postorder.slice(leftSubtreeSize, postorder.length - 1));
    return root;
};

Problem Description

Given two integer arrays preorder and postorder that represent the preorder and postorder traversal of a binary tree, construct and return the binary tree that generated these traversals.
  • Each value in preorder and postorder is unique.
  • It is guaranteed that there is at least one valid binary tree that can be constructed from these traversals.
  • You must not reuse or duplicate any elements; each value represents a unique node.
  • Return the root node of the constructed binary tree.

Thought Process

At first glance, reconstructing a binary tree from traversals seems straightforward if given preorder and inorder (or postorder and inorder), since the inorder traversal gives a clear left/right subtree boundary. However, with only preorder and postorder, it's less obvious. The key insight is that:
  • preorder traversal visits nodes in root - left - right order.
  • postorder traversal visits nodes in left - right - root order.
By comparing the two traversals, we can deduce the boundaries of left and right subtrees at each recursive step. A brute-force approach would be to try every possible split, but this is inefficient. Instead, we look for the root of the left subtree (which is the next node in preorder after the root) in the postorder array, which tells us how many nodes are in the left subtree. This allows us to recursively build the tree efficiently.

Solution Approach

To construct the binary tree, we use recursion and the properties of preorder and postorder traversals.
  1. Base Case: If the preorder array is empty, return null (no nodes to construct).
  2. Root Node: The first element of preorder is always the root of the current subtree.
  3. Left Subtree: If there are more elements, the second element in preorder is the root of the left subtree. Find this value in postorder to determine the size of the left subtree (since postorder lists all left subtree nodes before the right subtree and root).
  4. Recursive Construction:
    • Recursively build the left subtree using the corresponding slices of preorder and postorder.
    • Recursively build the right subtree using the remaining elements.
  5. Return: Attach the constructed left and right subtrees to the root and return the root.
This approach ensures each node is created only once and leverages the unique properties of the traversals for efficient construction.

Example Walkthrough

Let's walk through an example:
  • preorder = [1, 2, 4, 5, 3, 6, 7]
  • postorder = [4, 5, 2, 6, 7, 3, 1]
  1. The first element in preorder is 1 (the root).
  2. The second element is 2 (root of the left subtree). Find 2 in postorder (index 2). So, the left subtree has 3 nodes (4, 5, 2).
  3. Recursively construct:
    • Left subtree: preorder[1:4] = [2, 4, 5], postorder[0:3] = [4, 5, 2]
    • Right subtree: preorder[4:] = [3, 6, 7], postorder[3:6] = [6, 7, 3]
  4. For the left subtree:
    • Root is 2, next is 4. 4 is at index 0 in postorder, so left subtree has 1 node.
    • Left: [4], [4] (returns node 4)
    • Right: [5], [5] (returns node 5)
    • Attach 4 and 5 as left and right children of 2.
  5. For the right subtree:
    • Root is 3, next is 6. 6 is at index 0 in postorder, so left subtree has 1 node.
    • Left: [6], [6] (returns node 6)
    • Right: [7], [7] (returns node 7)
    • Attach 6 and 7 as left and right children of 3.
  6. Finally, attach the left and right subtrees to root 1.
The constructed tree is:
  • 1
    • 2
      • 4
      • 5
    • 3
      • 6
      • 7

Time and Space Complexity

  • Brute-force approach: If we tried every possible split, the time complexity would be exponential, which is infeasible.
  • Optimized approach: Each node is processed exactly once, and for each node, we find the left subtree size by scanning postorder (which is O(n) per node in the naive implementation). With further optimization (using a hash map to store value-to-index mappings), we can reduce this to O(1) per lookup.
  • Time Complexity: O(n), where n is the number of nodes.
  • Space Complexity: O(n), due to recursion stack and storage for the node objects (and possibly the hash map).

Summary

In this problem, we leveraged the unique properties of preorder and postorder traversals to reconstruct the binary tree. The key insight is to identify subtree boundaries by matching the root of the left subtree in the postorder array. By recursively building the left and right subtrees, we efficiently construct the entire tree. The approach is both elegant and efficient, making use of recursion and traversal properties, and can be further optimized with hash maps for faster lookups.