Overview of Breadth and Depth first traversal in a Binary Tree.
keywords
programming2017-02-12
There are two main ways to process data within a binary tree. In this post, I go over some breadth-first and depth-first searching algorithms.
Here is a my attempt at a tree, which I will use as an example.
F
/ \
D H
/ \ / \
B E G J
In a breadth-first search, the elements of the tree are visited from left to right, and top to bottom, just like reading some text. The example tree would be evaluated as, {F, D, H, B, E, G, J}
.
In depth-first search, visiting a child node is visiting a complete subtree. There is more than one way to perform a depth-first search. Some of the most common are as follows:
root->left->right
(pre-order DFS traversal)
A pre-order DFS traversal of the example tree above would look like this: {F, D, B, E, H, G, J}
.
left->root->right
(in-order DFS traversal)
An in-order DFS traversal of the example tree above would look like this: {B, D, E, F, G, H, J }
.
left->right->root
(post-order DFS traversal)
Finally, a post-order DFS traversal of the example tree above would look like: {B, E, D, G, J H, F}
.
Just to give these different ways of traversing a binary tree some context, take mathematical expressions as an example. The operators are the leaf nodes, and the operands are the nodes with one or two subtrees.
*
/ \
- +
/ \ / \
2 3 7 10
When it comes to writing math expressions, there are actually a few different ways to do so. Polish notation, also known as prefix notation, is when the operators are written on the left of the operands (+ 3 2
for example.) Similarly, reverse Polish notation is where the operators are written to the right of the operands (3 2 +
).
Traversing an expression tree using an in-order DFS algorithm produces an expression like most of us are used to. The above example would come out to be: (2 - 3) * (7 + 10)
.
Going through the expression tree using pre-order DFS produces the Polish notation version of the same expression: * - 2 3 + 7 10
Finally, a post-order DFS produces the reverse Polish notation: 2 3 - 7 10 + *
Pretty Neat.
Now here is some Go code to traverse the binary tree. A node looks like this:
type node struct {
value string
left *node
right *node
}
And here are the different DFS traversal algorithms:
/* pre-oder DFS traversal */
func preorder(n *node) *node {
if n != nil {
fmt.Printf(n.value + " ")
preorder(n.left)
preorder(n.right)
}
return n
}
/* in-oder DFS traversal */
func inorder(n *node) {
if n != nil {
inorder(n.left)
fmt.Printf(n.value + " ")
inorder(n.right)
}
}
/* post-oder DFS traversal */
func postorder(n *node) {
if n != nil {
postorder(n.left)
postorder(n.right)
fmt.Printf(n.value + " ")
}
}
To traverse a binary tree from top to bottom and right to left, we will need the help of a queue to keep track of the elements that need to be visited next. That’s because any given element in the tree does not have a pointer to any of the other elements on the same level. The algorithm follows this general pattern:
enqueue the element.
while the queue is not empty...
dequeue a element
process the element
enqueue the element's left and right children
done
Here’s what it might look like in Go:
/* breadth first traversal */
func breadth(n *node) {
if n != nil {
s := []*node{n}
for len(s) > 0 {
current_node := s[0]
fmt.Printf(current_node.value + " ")
s = s[1:]
if current_node.left != nil {
s = append(s, current_node.left)
}
if current_node.right != nil {
s = append(s, current_node.right)
}
}
}
}
Code from this post can be found here.