Wikipedia

Binary search treesare a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. When inserting orsearchingfor an element in abinary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found.

### Important Definitions

**Binary Tree**: A tree that starts at a single root and branches down, all nodes have a minimum of 0 children (leaves) and a maximum of 2 children.**Complete Binary Tree**: All levels are full except at the bottom level, all levels are filled left to right.**Full Binary Tree**: All nodes have 2 children or 0 children (leaf).**Binary Search Tree**: A binary tree with the **Search Tree Property.****Search Tree Property: **For any node x, all nodes in it’s left subtree are less than x and all nodes in its right subtree are greater than or equal to x.

### Binary Search Tree Algorithms

defsearch(key, node):ifnodeisNoneornode.key == key:returnnodeifkey < node.key:returnsearch(key, node.left)else:returnsearch(key, node.right)

definsertion: - Search and insert where we fell off tree

deffind_min(node):ifnode.leftisNone:returnnodeelse:returnfind_min(node.left)

deffind_max(node):ifnode.rightisNone:returnnodeelse:returnfind_max(node. right)

defsuccessor(node):ifnode.right:returnfind_min(node.right)else:Go up until you find a node with it's parent on the right, return parent

defdelete(node):ifnode is leaf:deletenodeifnode has one child:connectnode parent to node childdeletenodeifnode has 2 children:swapnode withsuccessor(node)delete(node)

**Runtime Complexity**Search: O(h)

Insert: O(h)

Find Min: O(h)

Find Max: O(h)

Successor: O(h)

Delete: O(h)

h can range from

O( log (n) ) – Best Case, Balanced BST

O(n) – Worst Case, Linked List BST