algoadvance

Leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal

Problem Statement

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example:

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]  // in the form of an in-order traversal for confirmation

Clarifying Questions

  1. Are all tree nodes guaranteed to have unique values?
    • Yes, all the node values are distinct.
  2. Can the binary tree be non-complete (i.e., nodes can have zero, one or two children)?
    • Yes, the binary tree can be of any form as long as preorder and postorder sequences match a valid binary tree.
  3. Is the input size bounded by any constraints?
    • The problem does not explicitly say, but typical constraints range from small inputs (like 1-1000 nodes).

Great, let’s move on to the strategy to solve this problem.

Strategy

  1. Understanding Preorder and Postorder:
    • Preorder: The order of nodes is Root -> Left Subtree -> Right Subtree.
    • Postorder: The order of nodes is Left Subtree -> Right Subtree -> Root.
  2. Recursive Approach:
    • Use the first element of preorder to identify the root of the tree.
    • The second element in the preorder will indicate the root of the left subtree.
    • Find this element in the postorder array to determine the boundary of the left subtree in both arrays.
    • Recursively repeat the process for the left and right subtrees until the tree is completely constructed.
  3. Base Cases:
    • If the range in preorder or postorder becomes invalid (start index > end index), return nullptr.

Code

Here’s how to implement this solution in C++:

#include <vector>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        unordered_map<int, int> postorder_map;
        for (int i = 0; i < postorder.size(); ++i) {
            postorder_map[postorder[i]] = i;
        }
        return construct(preorder, 0, preorder.size()-1, postorder_map, 0, postorder.size()-1);
    }
    
private:
    TreeNode* construct(const vector<int>& preorder, int pre_start, int pre_end,
                        const unordered_map<int, int>& postorder_map, int post_start, int post_end) {
        if (pre_start > pre_end || post_start > post_end) {
            return nullptr; 
        }

        TreeNode* root = new TreeNode(preorder[pre_start]);

        if (pre_start == pre_end) { // No more children
            return root;
        }

        int left_root_val = preorder[pre_start + 1];
        int left_subtree_size = postorder_map.at(left_root_val) - post_start + 1;

        root->left = construct(preorder, pre_start + 1, pre_start + left_subtree_size, postorder_map, post_start, post_start + left_subtree_size - 1);
        root->right = construct(preorder, pre_start + left_subtree_size + 1, pre_end, postorder_map, post_start + left_subtree_size, post_end - 1);

        return root;
    }
};

Time Complexity

The time complexity analysis of this algorithm is as follows:

Thus, the overall time complexity is O(n), where n is the number of nodes in the tree. Each node is processed in constant time during the construction of the tree.

This solution is efficient and handles the problem constraints well.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI