Binary Search Trees
Course launching November 17, 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
A binary search tree is a special implementation of a binary tree and are commonly used for tree interview questions. As with a binary tree, each node can have at most two children. Additionally, we call it a "search" tree because build it get fast data access in O(log n) time.
It is intentionally constructed in ascending order starting with the left-most leaf node as the smallest value and the right-most leaf as the largest value. This means at any node in the tree, all the children to its left will be smaller, and all the children to its right will be larger. By doing this, we are able to get O(log n) operations.
|Big O Complexity|
- Fast O(log n) for all operationsAssuming we have a balanced tree, all of our operations are fast
- OrderedWe maintain a BST in order
- Flexible SizeData does need to be sequential in memory. We can arbitrarily add/remove items on a tree as long as we have a way to point to the next item.
- Must Maintain BalanceIf the BST isn't balanced, it degrades to O(n) time
Binary Search Trees in Interviews
- Recognize you can get a solution O(log n) with a BST
- Validate a binary search tree
- Build a binary search tree or convert to/from another data dataStructure
- Find position of element based on order
Binary Search Trees Explained
Let's break down the definition of a binary search tree:
Binary Tree: Any node can have at-most two children by using a left and right pointer
Binary Search: You can perform binary search on the tree because nodes are ordered
So a binary search tree is a sorted binary tree.
This means with a BST, we have ordered data. Looking at any give node, if we follow its left child, all the items will be smaller than the current node. If we follow its right child, all the items will be larger.
When we see a BST in interviews, it often means two possible things:
- We want to make use of its ordering
- We want to perform operations in O(log n) time
The ordering is what separate this from a standard binary tree.
To achieve O(log n) time, the BST much be balanced. There isn't a strict definition of balanced, but it means that every time you traverse to a child, you eliminate approximately half of the remaining. Being able to divide the data by 2 on each step is exactly what it means to be O(log n)
The tree has
n = 28 total nodes, but we only need touch 5 of them to find value we want.
This is the power of O(log n) time and a balanced BST operations.
If our tree is unbalanced, and there is a long path to the final node, and it will degrade to O(n).
This is because in a worst case to traverse the long branch of nodes, you must iterate through all
In the example of above, we have only
n = 8 nodes, but we must touch 6 in order to find the value.
If we had many more nodes, this would look much worse and is why it's essential to have a balanced tree.
It is not very common to need to actually balance a tree in an interview, but you should still be prepared to discuss why it's required to achieve O(log n). In production, you will likely use a library to implement balancing, and the two most common are AVL trees and red-black trees. Let's take a quick look at each.
AVL trees apply a weight to the nodes and will automatically rotate nodes to rebalance if the height of two child subtrees differ by more than one.
Each node in the tree stores an extra bit which the two states are referred to as red or black. The tree maintains balance by enforcing a specific arrangements of colors and will adjust as needed when new nodes are added.
Table of Contents