gen-briefly-explain-a-binary-search-tree-and-one-common-misconce-4c3d

Briefly explain a binary search tree and one common misconception about it.

# Binary Search Tree (BST) A **binary search tree** is a tree data structure where each node has at most two children (left and right), and it maintains a specific ordering property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. **Example:** ``` 8 / \ 3 10 / \ \ 1 6 14 ``` This ordering allows for efficient searching, insertion, and deletion with O(log n) average time complexity. ## Common Misconception **Misconception:** "A binary search tree is always balanced and guarantees O(log n) operations." **Reality:** BSTs can become **unbalanced** depending on insertion order. In the worst case (e.g., inserting sorted data), a BST degenerates into a linked list with O(n) time complexity. ``` Inserting 1, 2, 3, 4, 5 creates: 1 \ 2 \ 3 \ 4 \ 5 ``` Self-balancing trees like AVL or Red-Black trees are needed to guarantee O(log n) performance.