The Binary Search Tree is a data structure that store "items" (such as numbers, names etc.) in memory.
Binary Search Trees (BST) keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key (or a place to insert a new key) in a tree, they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each search, insert or delete takes time proportional to O(log(V)), where V is the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.
BST support three main operations: insert, delete and search elements.
| Average | Worst case | |
| space | Θ(n) | O(n) |
|---|---|---|
| search | Θ(log n) | O(n) |
| insert | Θ(log n) | O(n) |
| delete | Θ(log n) | O(n) |
As we can see in the previous Table, in the worst case the three operations has the same space and time complexities (linear); and in the average case the space complexity is linear and the complexities for the three operations are logarithmic.
The BST is a commonly questioned in many interviews. Here I presented my solutions for some interviews:
- Interview one: The exercise of this interview can be seen in this link [Exercise] and my solution in C++ can be downloaded from my [GitHub].
- Interview two: I did this interview for Google by Hangout. My solution in Java can be downloaded from my [GitHub].
Please, feel free to give me your comments :)
