# Binary Search Tree — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/bst

> A binary tree where left < node < right, giving ordered O(log n) search.

## The ordering invariant

For every node, all keys in its left subtree are smaller and all in its right are larger. So searching is like binary search: compare, then go left or right, halving the tree each step — `O(h)`.

## Search & insert

Both follow one path from the root; insert drops the new key where the search would have failed.

```python
def search(node, key):
    while node and node.val != key:
        node = node.left if key < node.val else node.right
    return node

def insert(node, key):
    if not node: return Node(key)
    if key < node.val: node.left = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## In-order = sorted

An in-order traversal of a BST yields keys in ascending order. That's a quick way to validate a BST or find the k-th smallest element.

**Quiz:** Insert 1,2,3,4,5 in order into an empty unbalanced BST. Search cost becomes...

- [ ] O(log n)
- [x] O(n)
- [ ] O(1)

*Answer:* O(n). Sorted inserts create a right-leaning chain — effectively a linked list. Balanced trees (AVL, red-black) fix this.