Binary Search Trees & Tree Traversal

Today I’m going to cover the two most common ways of traversing or iterating through the contents of a data structure known as a?Binary Search Tree. These are known as Breadth First Traversal (BFT) and Depth First Traversal (DFT). But before we get started

What is a Binary Search Tree?

A binary search tree is a data structure composed of nodes that each contain a piece of data, and a reference to two child nodes, the left child and the right child. The left child node’s data must always be smaller than the data of the parent node, and the right child node’s data must be larger than that of the parent node. Also, something important to note, when creating a binary search tree we must define a root node, which represents the base of the tree and thus the midpoint of all of the other nodes’ values. We end up with a tree structure of nodes, each with two children at the most.

As you can see, the right side of the tree contains nodes with data values that are all larger than the root node, and the left side contains nodes with data values that are all smaller than the root node.

Breadth First Traversal (BFT)

Breadth first traversal is a technique for traveling through a tree data structure by moving from the left to right through each row of nodes and down to the next row after the current row is complete. Here’s a nice illustration for clarity:

We travel from the root node ‘F’ down to the next row and reach ‘B’ after that ‘G’, then continue to the next row and hit ‘A’, ‘D’, then ‘I’ and so on. Breadth first search is a great tool to reach for if you are looking to find a node that is somewhat close to the root node.

Depth First Traversal (DFT)

Depth first traversal, the other common tool for moving through the elements of a tree, is done by first traveling down the left most branch of the tree until it hits the bottom of the tree. Once at the bottom, it will operate on each sibling of the left most child of the tree. Then the process will travel back up to the closest parent node, then operate on the next child of that node and all of its descendants. It continues to move down each path of the tree to the very bottom until all paths have been traveled. A bit confusing when written, but here’s a clear diagram:

The depth-first traversal path is simple to understand if you follow the path of the dotted line. It goes from left to right, scanning every branch for its deepest point before moving on. If you are looking for a node in your tree that could be extremely far down in the tree structure, depth-first search is fantastic.

I've finished my tour of the binary tree traversal! I hope this enables you to climb some digital trees like the real Donkey Kong ;)