6.Construct Binary Search Tree from Preorder Traversal

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

Solution Tree

Iterative Solution:-

• Searching the position and then inserting

class Solution
{
public:
    TreeNode *bstFromPreorder(vector<int> &preorder)
    {

        TreeNode *root = NULL;

        for (int i = 0; i < preorder.size(); i++)
        {
            int n = preorder[i];
            if (root == NULL)
            {
                TreeNode *temp = new TreeNode;
                temp->val = n;
                temp->left = NULL;
                temp->right = NULL;
                root = temp;
            }
            else
            {
                TreeNode *p = root;
                TreeNode *q = NULL;
                while (p != NULL)
                {
                    q = p;
                    if (p->val == n)
                    {
                        break;
                    }
                    else if (p->val > n)
                    {
                        p = p->left;
                    }
                    else
                    {
                        p = p->right;
                    }
                }

                TreeNode *temp = new TreeNode;
                temp->val = n;
                temp->left = NULL;
                temp->right = NULL;
                if (n < q->val)
                {
                    q->left = temp;
                }
                else
                {
                    q->right = temp;
                }
            }
        }
        return root;
    }
};

Time Complexity: O(n^2) or O(n log(n))

Optimized Solution using stack

class Solution
{
public:
    TreeNode *bstFromPreorder(vector<int> &preorder)
    {

        TreeNode *root = NULL;
        TreeNode *p = NULL;
        stack<TreeNode *> s;

        TreeNode *temp = new TreeNode;
        temp->val = preorder[0];
        temp->left = NULL;
        temp->right = NULL;
        root = temp;
        p = root;

        int i = 1;
        while (i < preorder.size())
        {
            int n = preorder[i];

            TreeNode *temp = new TreeNode;
            temp->val = n;
            temp->left = NULL;
            temp->right = NULL;

            if (n < p->val)
            {
                p->left = temp;
                s.push(p);
                p = p->left;
                i++;
            }
            else if (n > p->val)
            {
                if (!s.empty())
                {
                    TreeNode *q = s.top();
                    if (n < q->val)
                    {
                        p->right = temp;
                        p = p->right;
                        i++;
                    }
                    else
                    {
                        p = s.top();
                        s.pop();
                    }
                }
                else
                {
                    p->right = temp;
                    p = p->right;
                    i++;
                }
            }
        }

        return root;
    }
};

Time Complexity: O(n)