The Basics of Binary Search Trees
As I prepare myself for technical interviews, I have crossed paths with a common data structure known as a binary search tree. A binary search tree (BST) is simpler than what the name suggests. Let us breakdown what BSTs are and an example on how they can be used.
Definition
A BST is a data structure in which each node has at most two children. The value of each left node is less than its parent, while the value of each right node is greater than its parent. We can think of a BST like an upside-down tree. The root of the tree is the topmost node. The parent is the branch of the tree. This branch can have two other branches coming off them which are the child nodes. The two child nodes that are attached to the same parent node are siblings. These branches can have leaves. A leaf node has no children nodes and ends that section of the branch.
Following the above example, we see that our root node has a value of 22. The left child node has a value of 13, less than 22, and the right child node has a value of 30, more than 22. As we continue down the tree, all the child nodes on the left side must have a smaller value than their parent node, and all the child nodes on the right side of each node must have a bigger value than their parent node. As stated earlier, each node has at most two child nodes.
Searching Values in a BST
Let us say we want to search for a certain value in this Binary search tree above. We want to find the node with a value of 15. We can first ask is 15 greater than or less than 22? 15 is less than 22 so we know we will be on the left side. We ignore the right side of the root and move on to the left side.
We check if this node as the same value as our target node. No, 15 does not equal 13. We ask ourselves these same questions as we go. 15 is greater than 13, so we go right. Next row, we check again if 15 equals 18. We see that it does not, it is actually less than 18, so we go left. We check to see if the value of the node is 15 and it is! We can return that we have found the node.
Inserting Values in a BST
Inserting a node works very similarly to how searches work. We start by checking if our root has child nodes. We then compare the value we wish to insert to our root node, checking whether it’s bigger or smaller. Let’s say we want to add a node with a value of 23.
We can follow the same steps. We see that our root has both of their child nodes. Our new node has a value of 23, greater than 15, so we will go down the right branch. The node with a value of 29 does not have any child nodes. We will insert our node to the left side since 23 is less than 29. We can follow this same pattern as the tree gets bigger.
Resources
For more resources on binary search trees, I suggest looking at these helpful links.
Really cool demo https://www.cs.usfca.edu/~galles/visualization/BST.html
https://medium.com/@ramyjzh/data-structures-for-dummies-binary-search-trees-13f87a1313a2
https://medium.com/swlh/understanding-data-structures-binary-search-trees-a6612daf00dd
https://www.geeksforgeeks.org/implementation-binary-search-tree-javascript/
