Construct a BST from a Preorder Traversal

Problem Statement

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., Binary Search Tree), construct the tree and returns its root.

Examples:

Example 1:

Input: preorder = [8, 5, 1, 7, 10, 12]
Output: [8, 5, 10, 1, 7, null, 12]

Example 2:

Input: preorder = [1, 3]
Output: [1, null, 3]

Different Approaches

1️⃣ Brute Force Approach

Intuition:

To build a Binary Search Tree (BST) from a preorder traversal, it's important to understand how BST properties work with preorder traversal. In a preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree. This means that the first element in the preorder array is the root of the BST. For the subsequent elements, any number smaller than the root should go to the left subtree, and any number larger should go to the right subtree.

Visualizing this can help: imagine you are planting a tree, and the first seed you plant is the root. Every next seed you plant has to follow the rule: if it's smaller, it goes to the left; if it's larger, it goes to the right. This keeps the tree ordered and balanced.

Approach:

The first element of the preorder array is the root of the BST.
For each subsequent element in the preorder array, determine its position in the BST based on the following rules:
1. If the element is smaller than the root, it goes to the left subtree.
2. If the element is larger than the root, it goes to the right subtree.
Repeat the process for each subtree, treating the current node as the new root and inserting elements to its left or right as appropriate.

Code:

#include<bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        // Check if the preorder list is empty
        if (preorder.empty()) return nullptr;

        // The first element is the root
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> s;
        s.push(root);

        // Iterate through the rest of the elements
        for (int i = 1; i < preorder.size(); ++i) {
            TreeNode* node = s.top();
            TreeNode* child = new TreeNode(preorder[i]);

            // Adjust the stack and place the node in the right position
            while (!s.empty() && s.top()->data < preorder[i]) {
                node = s.top();
                s.pop();
            }

            // Insert node as left or right child
            if (node->data < preorder[i]) {
                node->right = child;
            } else {
                node->left = child;
            }

            // Push the child node to the stack
            s.push(child);
        }

        return root;
    }
};

// Function to print the tree in-order for testing
void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    Solution solution;
    vector<int> preorder = {8, 5, 1, 7, 10, 12};

    TreeNode* root = solution.bstFromPreorder(preorder);

    // Print the constructed BST
    inorderTraversal(root);

    return 0;
}

Complexity Analysis:

Time Complexity:O(N) as each element is processed once.
Space Complexity:O(N) due to the stack storing nodes.

2️⃣ Better Approach

Intuition:

To build a Binary Search Tree (BST) from a preorder traversal, we need to use the properties of BSTs. In a BST, the left subtree of a node contains only nodes with values less than the node's value, and the right subtree only nodes with values greater than the node's value. The preorder traversal visits nodes in the order: root, left subtree, right subtree. By combining preorder and inorder traversals, we can uniquely determine the structure of the tree.

Approach:

Sort the Preorder Array since the sorted version of the preorder array will give the inorder traversal of the BST.
With both preorder and inorder arrays, construct the BST by recursively determining the root and its subtrees.
Recursive Tree Construction: Use a helper function to recursively build the tree:
1. If the start indices exceed the end indices, return null.
2. The first element in the current preorder range is the root. In the preorder traversal of a binary tree, the root of the tree or subtree is always the first element of the current segment.
3. Once the root node is identified, it is necessary to find its position in the inorder array. The inorder traversal provides information about the relative positions of the left and right subtrees. The elements to the left of the root in the inorder array will form the left subtree, while the elements to the right of the root will form the right subtree. This step involves using a map (created from the inorder array) to quickly locate the index of the root element and determine the size of the left subtree.
4. Recursively build the left and right subtrees using the determined indices. For the left subtree, we adjust the indices to include only the elements that fall before the root in the inorder array, and similarly for the right subtree, we include only the elements that fall after the root. This recursive process continues until the entire tree is constructed.

Code:


#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        // Convert preorder to inorder by sorting
        vector<int> inorder = preorder;
        sort(inorder.begin(), inorder.end());

        // Create a map to store indices of elements in the inorder traversal
        unordered_map<int, int> inMap;
        for (int i = 0; i < inorder.size(); ++i) {
            inMap[inorder[i]] = i;
        }
        
        // Helper function to build the tree
        return buildTree(preorder, inMap, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

private:
    TreeNode* buildTree(const vector<int>& preorder, unordered_map<int, int>& inMap,
                        int preStart, int preEnd, int inStart, int inEnd) {
        // Base case: if the start indices exceed the end indices, return nullptr
        if (preStart > preEnd || inStart > inEnd) return nullptr;

        // Create the root node with the value at the current preorder index
        TreeNode* root = new TreeNode(preorder[preStart]);
        int inRoot = inMap[root->data];
        int numsLeft = inRoot - inStart;

        // Recursively build the left and right subtrees
        root->left = buildTree(preorder, inMap, preStart + 1, preStart + numsLeft, inStart, inRoot - 1);
        root->right = buildTree(preorder, inMap, preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd);

        return root;
    }
};

// Main function for testing
int main() {
    Solution sol;
    vector<int> preorder = {3, 9, 20, 15, 7};
    
    // Convert preorder to inorder by sorting
    vector<int> inorder = preorder;
    sort(inorder.begin(), inorder.end());
    
    TreeNode* root = sol.bstFromPreorder(preorder);
    
    // Function to print inorder traversal of the tree (for verification)
    function<void(TreeNode*)> printInorder = [&](TreeNode* node) {
        if (node) {
            printInorder(node->left);
            cout << node->data << " ";
            printInorder(node->right);
        }
    };

    cout << "Inorder of Unique Binary Tree Created:" << endl;
    printInorder(root);
    cout << endl;

    return 0;
}

Complexity Analysis:

Time Complexity:O(N log N) due to sorting and O(N) for tree construction.
Space Complexity:O(N) for the inorder list and the recursion stack.

3️⃣ Optimal Approach

Intuition:

To solve the problem of constructing a Binary Search Tree (BST) from a preorder traversal, it is essential to understand the properties of BSTs and the nature of preorder traversal. The key steps involve identifying the root, and then recursively constructing the left and right subtrees within the bounds defined by the BST properties. The first element in the preorder traversal list is always the root of the BST. Elements that appear after the root in the preorder list and are smaller than the root belong to the left subtree. Elements that appear after the root and are greater than the root belong to the right subtree. Recursively apply this logic to construct the entire BST.

The thought process involves recognizing that the preorder traversal provides a natural order to build the tree and using the BST properties to maintain the structure. To proceed first determine the range for constructing the subtrees maintaining an upper bound. For the left subtree, the upper bound is the value of the root, and for the right subtree, the upper bound remains the same as the initial one. This ensures that each subtree respects the BST property where left children are smaller than the root and right children are greater.

Approach:

Initialize an index pointer starting at the beginning of the preorder list.
Define a recursive function that constructs the BST by taking the current index, the preorder list, and an upper bound as parameters.
If the current index exceeds the length of the preorder list or the current element exceeds the upper bound, return null.
Create a new tree node with the current element and increment the index.
Recursively construct the left subtree with the updated index and the current element as the new upper bound.
Recursively construct the right subtree with the updated index and the original upper bound.
Return the constructed tree node.

Code:

#include<bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
 struct TreeNode {
     int data;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
 };

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        // Start the recursive function with the first element as the root
        // and the entire range of valid numbers
        int index = 0; // Initialize index
        return bstFromPreorderHelper(preorder, INT_MAX, index);
    }

private:
    TreeNode* bstFromPreorderHelper(vector<int>& preorder, int bound, int& index) {
        // If all elements are used or the next element
        // is greater than the bound, return null
        if (index == preorder.size() || preorder[index] > bound) return nullptr;

        // Create a new TreeNode with the current value
        TreeNode* root = new TreeNode(preorder[index++]);

        // Recursively construct the left subtree
        // with the current value as the new bound
        root->left = bstFromPreorderHelper(preorder, root->data, index);

        // Recursively construct the right subtree
        // with the same bound as the parent's bound
        root->right = bstFromPreorderHelper(preorder, bound, index);

        // Return the constructed subtree's root
        return root;
    }
};

// Example usage
int main() {
    Solution solution;
    vector<int> preorder = {8, 5, 1, 7, 10, 12};
    TreeNode* bst = solution.bstFromPreorder(preorder);
    // Add code to print or use the bst as needed
    return 0;
}

Complexity Analysis:

Time Complexity:O(N) due to visiting each node once in the preorder traversal.
Space Complexity:O(h) where h is the height of the tree due to recursion stack.

Problem Statement

Examples:

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Approach:

Code:

Complexity Analysis:

2️⃣ Better Approach

Intuition:

Approach:

Code:

Complexity Analysis:

3️⃣ Optimal Approach

Intuition:

Approach:

Code:

Complexity Analysis:

About me

Popular Posts

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory

Quick links

Tags

Newsletter

🛠️ Settings

Problem Statement

Examples:

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Approach:

Code:

Complexity Analysis:

2️⃣ Better Approach

Intuition:

Approach:

Code:

Complexity Analysis:

3️⃣ Optimal Approach

Intuition:

Approach:

Code:

Complexity Analysis:

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory