Binary Search Trees (BST)

A Binary Search Tree is a tree data structure where each node has at most two children, and the nodes are sorted: everything to the Left is smaller, and everything to the Right is larger. This allows for searching in O(Log N) time.

1. Why use a Tree?

In an unsorted array, searching takes O(N). In a sorted array, searching takes O(Log N), but inserting takes O(N). A BST gives you the best of both worlds: O(Log N) search AND O(Log N) insertion (if the tree stays balanced).

2. Tree Traversal

• In-Order (LDR): Returns the values in perfectly sorted order.
• Pre-Order (DLR): Useful for cloning a tree.
• Post-Order (LRD): Useful for deleting a tree (bottom-up).

3. The Worst-Case Scenario

If you insert sorted data (1, 2, 3, 4, 5) into a standard BST, it becomes a Skewed Tree (essentially a Linked List). The search time drops to O(N). This is why "Auto-Balancing" trees are used in production databases.

4. Interview Mastery

Q: "How do you find the 'Lowest Common Ancestor' of two nodes in a BST?"

Architect Answer: "You start at the Root. If both target nodes are smaller than the root, you move Left. If both are larger, you move Right. The moment you find a node where one target is to the left and the other is to the right (or the node is one of the targets itself), you have found the Lowest Common Ancestor. This is an O(H) time complexity solution where H is the height of the tree."