Construct Binary Search Tree from Preorder Traversal

LeetCode Q 1008 - Construct Binary Search Tree from Preorder Traversal

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

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

Note:

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

Solution:

Solutino 1: DFS

Code:

int index = 0;

public TreeNode bstFromPreorder(int[] preorder) {
  return dfs(preorder, Integer.MAX_VALUE);
}

private TreeNode dfs(int[] preorder, int maxLimit) {
  if (index >= preorder.length || preorder[index] > maxLimit) return null;

  TreeNode node = new TreeNode(preorder[index++]);

  node.left = dfs(preorder, node.val);
  node.right = dfs(preorder, maxLimit);

  return node;
}

Solutino 2: BFS

Code:

public TreeNode bstFromPreorder(int[] preorder) {
  TreeNode root = new TreeNode(preorder[0]);    
  Deque<TreeNode> stack = new ArrayDeque<>();
  stack.push(root);

  for (int i = 1; i < preorder.length; i++) {
    TreeNode n = new TreeNode(preorder[i]);

    if (!stack.isEmpty() && stack.peek().val > n.val) {
      stack.peek().left = n;
    } else {
      TreeNode pre = null;
      while (!stack.isEmpty() && stack.peek().val < n.val) {
      	pre = stack.pop();
      }

      pre.right = n;
    }

    stack.push(n);
  }
  
  return root;
}