Algorithm
Problem Name: 1008. Construct Binary Search Tree from Preorder Traversal
Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.
It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.
A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.
A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.
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]
Constraints:
1 <= preorder.length <= 1001 <= preorder[i] <= 1000- All the values of
preorderare unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct TreeNode* bstFromPreorder(int* preorder, int preorderSize) {
struct TreeNode *node;
int mid;
if (preorderSize == 0) return NULL;
node = malloc(sizeof(struct TreeNode));
//assert(node);
node->val = preorder[0];
mid = 1;
while (mid < preorderSize && preorder[mid] < node->val) {
mid ++;
}
node->left = bstFromPreorder(&preorder[1], mid - 1);
node->right = bstFromPreorder(&preorder[mid], preorderSize - mid);
return node;
}
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Stack < TreeNode> stack = new Stack<>();
stack.push(root);
for (int i = 1; i < preorder.length; i++) {
TreeNode node = stack.peek();
TreeNode child = new TreeNode(preorder[i]);
while (!stack.isEmpty() && stack.peek().val < child.val) {
node = stack.pop();
}
if (node.val < child.val) {
node.right = child;
} else {
node.left = child;
}
stack.push(child);
}
return root;
}
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
const bstFromPreorder = function(preorder) {
let i = 0;
return bstFromPreorder(preorder, Number.MAX_VALUE);
function bstFromPreorder(A, bound) {
if (i === A.length || A[i] > bound) return null;
let root = new TreeNode(A[i++]);
root.left = bstFromPreorder(A, root.val);
root.right = bstFromPreorder(A, bound);
return root;
}
};
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _1008_ConstructBinarySearchTreeFromPreorderTraversal
{
private int[] preorder;
private int index;
public TreeNode BstFromPreorder(int[] preorder)
{
this.preorder = preorder;
index = 0;
return Build(int.MinValue, int.MaxValue);
}
private TreeNode Build(int minValue, int maxValue)
{
if (index >= preorder.Length) return null;
var value = preorder[index];
if (value < minValue || value > maxValue)
return null;
var root = new TreeNode(value);
index++;
root.left = Build(minValue, value);
root.right = Build(value, maxValue);
return root;
}
}
}
Input
Output