Binary Search Trees: A Quick and Dirty Recap

I recently learned about Binary Search Trees. BSTs are a pretty useful data structure, in that they not only store data in sorted order, but the way they’re implemented allows for quick lookup, insert and remove operations all with a time complexity of O(log n) time.

Ok, so from what I understand, this is how it works:

A tree traversal is a special case of graph traversal, and they refer to the process by which each node in the tree is visited, but only once each. These traversals are further classified by the order in which they process or visit the nodes. There are several classification of orders, but I’ll be focusing on breadth-first search and depth-first search which has further classifications of in-order, pre-order, and post-order traversal.

Whew, that’s a lot of words! If I were to put all that in diagram form, it might look something like this:

yo, i heard you like trees so i made a tree of the tree on the medium formerly known as a tree

Binary Search Trees have a couple of special properties, those being:

1. Each node can only have two children.
2. Of the children, the smaller key is always stored in the left node and the larger value is always stored in the right node.

Code Sample demonstrating Insert operation on Binary Search Trees

Code Samples demonstrating Find/Search of Binary Search Trees

Terminology

Before I continue, let’s go over some terminology:

• Node: a unit of data, typically connected/linked to other nodes
• Key: every node has a key (and it’s value pair)
• Root: the top node of the tree, ancestor of all other proceeding nodes.
• Parent: a node with at least one child
• Child: the left or right node/subtree of a parent node
• Leaf: nodes with no children
• Left and Right: Remember: A left child node’s key will always be less than its parent node’s key and a right child node’s key will always be greater than its parent’s node key

Here’s another diagram:

we love a pop culture reference

There are two main methods of searching through a binary tree: Depth-First Search and Breadth-First Search. As you may have surmised through their names, one method goes in deep first, and the other casts its net wide.

Breadth First Search

Breadth First Search is implemented with a Queue and goes by level order.

Here’s a diagram for Breadth-First Search:

Level Order!

Depth-First Search

With Depth-First Search, it’s implemented with a Stack. Each node has a visitation sequence it follows. There are three different ways to traverse the depths.

- Pre-Order (nlr)
- In-Order (lnr)
- Post-Order (lrn)

Pre-Order Depth-First Search

With Pre-Order DFS, the sequence goes Node ⇒ Left ⇒Right, as in:

1. Visit the Node (note your visit)
2. Check for Left Node
3. Check for Right Node

Note the circled Right is the Node it cuts through

It’s important to note here that this sequence is for each node and because DFS uses a stack, that means that for every node with a left child, it will continue to travel deeper to the left first before ever getting to the right child of the parent.

In-Order Depth-First Search

With In-Order DFS, the sequence goes Left ⇒ Node ⇒ Right:

1. From given/current node: check for Left child,

2a. (If no left child) visit Node
2b. (If yes left child), Repeat from Step 1

3. Check for right child

4. Repeat from Step 1

Somehow made it.. worse..? Should animate this, may make more sense..

So you can see how this is a stack implementation because it stacks up until the condition (visit a leaf node) is fulfilled/cleared from the stack before it processes the rest of the stack.

Also with In-Order DFS, because of the unique Binary Search Tree properties of the left always being smaller and the right being greater, you will always get a return output that is sorted in increasing numerical order.

Post-Order Depth-First Search

Finally we get to Post-Order DFS! This sequence goes Left ⇒ Right ⇒Node.

1. Starting from current node: is there a left node?
2. Yes? Check if that one has a left node. If yes, (keep going until there’s no left node)
3. Ok, no left node, is there a right node? No? Ok visit that node.
4. Now backtrack and where we we last? Oh yeah, is there a right node? Yes?
5. Ok proceed with step 1 (yay recursion)

Last diagram because words are hard:

Chaos is how I learn! [https://www.instagram.com/p/Bz0ZaqtFqiu/]

Ok… maybe words are hard but diagrams may be harder.

The diagrams may make it seem unnecessarily complex (which they are), but I found a great video demonstrating these traversals in action, which is magnitudes easier to pick up than static diagrams (in particular, mine).

Check it out here: https://www.youtube.com/watch?v=BHB0B1jFKQc

Sources:

(All diagrams created fresh for this article)

GROOT is a trademark of Marvel Characters, Inc. LEIF is a character on ANIMAL CROSSING which is a trademark of Nintendo of America Inc. I do not own these characters. Please don’t sue me.

Binary Search Trees - Wikipedia: https://en.wikipedia.org/wiki/Binary_search_tree

Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal. - Back to Back SWE: https://www.youtube.com/watch?v=BHB0B1jFKQc