Tags: "leetcode", "bst", access_time 2-min read

# Construct Binary Search Tree From Preorder Traversal

#### Created: April 20, 2020 by [lek-tin]

##### Last updated: April 20, 2020

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of `node.left` has a `value < node.val`, and any descendant of `node.right` has a `value > node.val`. Also recall that a preorder traversal displays the value of the node first, then traverses `node.left`, then traverses `node.right`.)

### Example 1

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

#### Note:

1. `1 <= preorder.length <= 100`
2. The values of preorder are distinct.

### Solution (stack)

Time: `O(n)`
Space: `O(n)`

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return null;
}

TreeNode root = new TreeNode(preorder[0]);
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);

// each node will be added and popped only ONCE
for (int i = 1; i < preorder.length; i++) {
TreeNode node = new TreeNode(preorder[i]);
if (node.val < stack.peek().val) {
stack.peek().left = node;
} else {
TreeNode pop = new TreeNode();
// traverse upward to find the root parent
while (!stack.empty() && stack.peek().val < node.val) {
pop = stack.pop();
}
pop.right = node;
}
stack.push(node);
}

return root;
}
}
``````

### Solution (recursion)

Time: `O(n)`
Space: `O(n)`

``````import java.lang.*;

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int preIndex = 0;

public TreeNode bstFromPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return null;
}

return dfs(preorder, preorder[0], Integer.MIN_VALUE, Integer.MAX_VALUE, preorder.length);
}

private TreeNode dfs(int[] preorder, int rootVal, Integer min, Integer max, int size) {
// base case
if (preIndex >= size) {
return null;
}

TreeNode root = null;

if (preorder[preIndex] > min && preorder[preIndex] < max) {
root = new TreeNode(rootVal);
// update preIndex
preIndex++;

if (preIndex < size)  {
root.left = dfs(preorder, preorder[preIndex], min, rootVal, size);
}
if (preIndex < size)  {
root.right = dfs(preorder, preorder[preIndex], rootVal, max, size);
}

return root;
}

return root;
}
}
``````