# Binary Search Tree — डेटा स्ट्रक्चर और एल्गोरिदम

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

> Binary tree जहाँ left < node < right, क्रमबद्ध O(log n) search देता है।

## क्रम अपरिवर्तनीय

हर node के लिए, उसके left subtree की सभी keys छोटी और right की सभी बड़ी। तो search binary search जैसा है: तुलना करें, फिर left या right जाएँ, हर चरण में tree आधा — `O(h)`।

## Search और insert

दोनों root से एक पथ का अनुसरण करते हैं; insert नई key वहाँ रखता है जहाँ search असफल होता।

```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 = क्रमबद्ध

BST का in-order traversal keys को आरोही क्रम में देता है। यह BST सत्यापित करने या k-वाँ सबसे छोटा तत्व खोजने का तेज़ तरीका है।

**Quiz:** खाली असंतुलित BST में 1,2,3,4,5 क्रम में डालें। Search लागत हो जाती है...

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

*Answer:* O(n). क्रमबद्ध insert दाईं ओर झुकी श्रृंखला बनाते हैं — असल में linked list। संतुलित trees (AVL, red-black) इसे ठीक करते हैं।