Construct Binary Search Tree from Preorder Traversal

Problem Statement

In this challenge, you are provided with an array of integers that represent the preorder traversal of a binary search tree (BST). Your task is to construct the BST from this preorder traversal and return the root of the tree. By the nature of BSTs, each node must ensure that any nodes on its left have values less than the node's value, and any nodes on its right have values greater.

Preorder traversal is a type of depth-first traversal where each node is processed before its child nodes. In other terms, for any node, the sequence in which the nodes are processed is: the node itself first, then the left subtree, and finally, the right subtree.

The problem guarantees that constructing a BST from the given preorder sequence is always feasible within the constraints provided, making it a straightforward application of tree construction principles using given preorder data.

Examples

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 <= 100
• 1 <= preorder[i] <= 1000
• All the values of preorder are unique.

Approach and Intuition

The given problem is about reconstructing a binary search tree (BST) from its preorder traversal list. Here’s a detailed breakdown of the approach and the intuition behind solving this problem:

1. Understanding Preorder Traversal:

   • In preorder traversal of a BST, the root node is visited first, followed by the left subtree and then the right subtree. This sequence provides clues about the hierarchy and relationship between different nodes.

2. Using a Stack for Construction:

   • You can leverage a stack to keep track of nodes. Start with pushing the first element (root) from the preorder list to the stack.
   • Iterate through the preorder list:
     • For each new node, if the node has a value less than the stack's top node, link this as the left child and push it to the stack.
     • If the node has a value greater than the stack's top node, pop the stack until you find a node with a greater value, which becomes the parent node for the current node. Then, link this as the right child and push the current node onto the stack.

3. Edge Cases and Complexity:

   • Ensure handling when the stack becomes empty.
   • The approach generally runs in O(n) time complexity, as each node is pushed and popped from the stack at most once.

4. Constraints Considerations:

   • Given the length constraint (1 to 100) and value constraints (1 to 1000) with all unique values, the method remains efficient and simple.

By this method, each element from the preorder list is processed exactly once, making it a linear time complexity solution which fits well within the problem's constraints. This ensures a quick and efficient construction of the BST from its preorder traversal data.

Solutions

class Solution {
  public TreeNode constructBSTFromPreorder(int[] preorderValues) {
    int size = preorderValues.length;
    if (size == 0) return null;
    
    TreeNode rootNode = new TreeNode(preorderValues[0]);
    Deque<TreeNode> nodesStack = new LinkedList<TreeNode>();
    nodesStack.push(rootNode);
    
    for (int idx = 1; idx < size; idx++) {
      TreeNode tempNode = nodesStack.peek();
      TreeNode newNode = new TreeNode(preorderValues[idx]);
    
      // Re-adjust the tree structure based on the preorder values
      while (!nodesStack.isEmpty() && nodesStack.peek().val < newNode.val)
        tempNode = nodesStack.pop();
    
      // Assign left or right child based on the BST property
      if (tempNode.val < newNode.val) tempNode.right = newNode;
      else tempNode.left = newNode;
    
      // Push the new node to stack
      nodesStack.push(newNode);
    }
    return rootNode;
  }
}