Construct Binary Search Tree from Preorder Traversal: สร้าง BST จาก Preorder

โจทย์

กำหนด Preorder traversal ของ BST สร้าง BST คืน root

BST property: Left subtree < Node < Right subtree

Preorder: Root → Left → Right

ตัวอย่าง: [8,5,1,7,10,12] → BST:

      8
     / \
    5   10
   / \    \
  1   7    12

อัลกอริทึม: Stack-based (Iterative) - O(n)

ใช้ Stack เก็บ "path" จาก root ไป current node

1. Root = preorder[0], push stack
2. For each value ใน preorder[1:]:
   • สร้าง node ใหม่
   • ถ้า value < stack[-1].val → เป็น left child ของ stack[-1], push
   • Else: Pop stack จนกว่า stack[-1].val > value (หา parent สำหรับ right child)
   • Last popped = parent, attach as right child, push new node

การติดตั้ง (Python Implementation)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> TreeNode:
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        stack = [root]
        
        for val in preorder[1:]:
            node = TreeNode(val)
            
            if val < stack[-1].val:
                # Left child of current top
                stack[-1].left = node
                stack.append(node)
            else:
                # Find parent for right child
                parent = None
                while stack and val > stack[-1].val:
                    parent = stack.pop()
                # parent is the last popped (largest smaller than val)
                parent.right = node
                stack.append(node)
        
        return root

# Helper: Print inorder (should be sorted for BST)
def inorder(node):
    if not node:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

# ทดสอบ
ob = Solution()
root = ob.bstFromPreorder([8,5,1,7,10,12])
print(inorder(root))  # [1, 5, 7, 8, 10, 12] ✓ (sorted)

# ทดสอบเพิ่ม
root2 = ob.bstFromPreorder([4,2,1,3,6,5,7])
print(inorder(root2))  # [1, 2, 3, 4, 5, 6, 7] ✓

Output

[1, 5, 7, 8, 10, 12]
[1, 2, 3, 4, 5, 6, 7]

Alternative: Recursive (Divide & Conquer) - O(n²) worst case

def bstFromPreorder_recursive(preorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    # Find first element > root (start of right subtree)
    i = 1
    while i < len(preorder) and preorder[i] < root.val:
        i += 1
    root.left = bstFromPreorder_recursive(preorder[1:i])
    root.right = bstFromPreorder_recursive(preorder[i:])
    return root

Complexity

• Stack (Iterative): O(n) time, O(n) space (worst case skewed tree)
• Recursive: O(n²) worst case (skewed), O(n log n) average

สรุป

Construct BST from Preorder ใช้ Stack iterative O(n) เหมาะกว่า Recursive เพราะไม่ต้องหา split point ทุกครั้ง Stack เก็บ ancestors ที่ยังไม่ได้ attach right child

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ