_1008. Construct Binary Search Tree from Preorder Traversal.md

1008. Construct Binary Search Tree from Preorder Traversal

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 27, 2024

Last updated : June 27, 2024

---

Related Topics : Array, Stack, Tree, Binary Search Tree, Monotonic Stack, Binary Tree

Acceptance Rate : 82.59 %

---

Solutions

• m1008 Recursion.java
• m1008.c
• m1008.cpp

Java

m1008 Recursion.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        bstHelper(preorder, root, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);

        return root;
    }

    private int bstHelper(int[] preorder, TreeNode curr, int indx, int lowerbound, int upperbound) {
        if (indx >= preorder.length) {
            return indx;
        }

        if (lowerbound < preorder[indx] && preorder[indx] < curr.val) {
            curr.left = new TreeNode(preorder[indx]);
            indx = bstHelper(preorder, curr.left, indx + 1, lowerbound, curr.val);
        }
        
        if (indx >= preorder.length) {
            return indx;
        }
        
        if (preorder[indx] < upperbound && preorder[indx] > curr.val) {
            curr.right = new TreeNode(preorder[indx]);
            indx = bstHelper(preorder, curr.right, indx + 1, curr.val, upperbound);
        }

        return indx;
    }
}

C

m1008.c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int bstHelper(int* preorder, int preorderSize, struct TreeNode* curr, int indx, int lowerbound, int upperbound) {
    if (indx >= preorderSize) {
        return indx;
    }
    
    if (lowerbound < preorder[indx] && preorder[indx] < curr->val) {
        curr->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
        curr->left->val = preorder[indx];
        curr->left->left = NULL;
        curr->left->right = NULL;
        indx = bstHelper(preorder, preorderSize, curr->left, indx + 1, lowerbound, curr->val);
    }

    if (indx >= preorderSize) {
        return indx;
    }
    
    if (preorder[indx] < upperbound && preorder[indx] > curr->val) {
        curr->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
        curr->right->val = preorder[indx];
        curr->right->right = NULL;
        curr->right->left = NULL;
        indx = bstHelper(preorder, preorderSize, curr->right, indx + 1, curr->val, upperbound);
    }

    return indx;
}

struct TreeNode* bstFromPreorder(int* preorder, int preorderSize) {
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = preorder[0];
    root->left = NULL;
    root->right = NULL;
    bstHelper(preorder, preorderSize, root, 1, INT_MIN, INT_MAX);
    return root;
}

C++

m1008.cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode(preorder[0]);
        bstHelper(preorder, root, 1, INT_MIN, INT_MAX);
        return root;
    }

    int bstHelper(vector<int>& preorder, TreeNode* curr, int indx, int lowerbound, int upperbound) {
        if (indx >= preorder.size()) {
            return indx;
        }
        
        if (lowerbound < preorder[indx] && preorder[indx] < curr->val) {
            curr->left = new TreeNode(preorder[indx]);
            indx = bstHelper(preorder, curr->left, indx + 1, lowerbound, curr->val);
        }

        if (indx >= preorder.size()) {
            return indx;
        }

        if (preorder[indx] < upperbound && preorder[indx] > curr->val) {
            curr->right = new TreeNode(preorder[indx]);
            indx = bstHelper(preorder, curr->right, indx + 1, curr->val, upperbound);
        }
        

        return indx;
    }
};