Binary search trees are data structures for sets (although the non-repetition of elements can be relaxed in some applications). Each element has a numeric key, which is stored in the tree. When a node does not have a child, each child is "NIL" and called a leaf. Each node has two children and each leaf has no children. The binary search tree has the property that the left subtree is less than its parent and the right subtree is greater than its parent. ```mermaid flowchart TB A(25) --> L(20) & R(29) L --> L1(18) & L2(23) R --> R1("NIL") & R2(31) L1 --> L3(15) & L4(19) L2 --> L5(21) & L6(24) ``` The height of a binary search tree is the length of the longest path down the tree. Whether to count the leaves differs across different sources. In the worst case, the height of a binary search tree with $n$ nodes is $n$. In the best case, a perfectly balanced binary search tree has height of $\log_2(n)$. ## find Find in a binary search tree returns the pointer to the element or `None` if the element is not in the tree. ```python find(node, skey): if node == None: return node else: if node.key == skey.key: return node elif node.key < skey.key: find(node.left, skey) else: find(node.right, skey) ``` ## insert Insert is a simple update to find. If the element is not found, insert the element at the leaf where the node would have been found. ## delete Deleting a node with no children is trivial. To delete a node with one child, replace the node with its child. To delete a node with two children, we must find the successor of the node as its replacement in the tree. The successor can be found by stepping to the right once and then following the left path to the end of the tree. ## traversals Traversals or visitor patterns are operations that visit each node in the tree in some order. There are three flavors of traversals: * in-order (left, me, right): will print the nodes in sorted order * pre-order (me, left, right) * post-order (left, right, me)