A Binary Search Tree is a binary tree where each node contains a key and optional associated value. It allows particularly fast lookup, addition, and removal of items.
The nodes in a binary search tree must be have some properties:
- The left subtree of a particular node will always contain nodes with keys less than that node's key.
- The right subtree of a particular node will always contain nodes with keys greater than that node's key.
- The keys in binary search tree must be unique.
Time Complexity: O(d) for Find, Min, Max, Previous, Next, Add, Remove operations. The d in O(d) is the depth of the binary search tree.
