Tree Data Structures

Family Tree — FirstCry Parenting

As I explore the world of data structures and algorithms, it is only right that I document my understanding of tree structures by explaining the different ways to traverse a tree with iterative solutions

Trees

Trees are data structures that connect nodes in a parent-child relationship. Each parent node will have a pointer to their child node. This means that the parent will always know their child.

Binary Search Tree

A Binary Tree is a tree data structure in which each node has a least two children, which are referenced as the left and right child nodes. The consistency of a binary tree is that the left child nodes are of lesser value than the root and the right child nodes are of greater value than the root.

Four Ways To Traverse A Binary Search Tree

What Exactly Does Traverse Mean in Programming?

Traversing, (also sometimes called iterating), in programming simply means to “touch” and “visiting” from the root (top), to the left and right leaf nodes.

Pre-order Traverse

Preorder Traversal is when you visit the root first, you then traverse to the left subtree nodes. Finally, we traverse to the right subtree nodes.

function preorderTraversal(root){
does root exist?
create empty stack
create empty results
push root into stack
while(stack not empty){
let a current variable contain the popped off stack elements
push the current value into our results
any current children on left ? push that child into stack
any current children on right ? push that child into stack
}
return results
}

Pseudocode Explained

We need to find out if the root is empty/existing before doing anything else. In the event that it is empty, then we must return an empty array as a result.

Now if the root is not empty, we first have to create an empty stack — (a stack has a Last In First Out sequence) — this is where we will order our tree in the preorder fashion, which is to add the root/ top element of the tree into the stack as the last in.

Using a while loop, while the stack is not empty, create a variable called current and assign that to our currently popped off item that came from the stack. Then push() that element’s value into our results array.

While that is happening, we must look to the root’s left and right children nodes and push them into the stack until there are no more children. These elements eventually will also get popped off into our current variable and printed in our results array.

Diagram:

Preorder Traversal / Depth First Search

preorder traversal by Tushar Roy — Coding Made Simple

In-order Traverse

In-order Traversal does exactly as it sounds, you traverse the tree in order. Meaning, it will print the value of every node from smallest to greatest.

function inorderTraverse(root){
create a new stack
initialize an empty results array
check if the root is empty or not
initialize a current variable to the root
keep looping as long as current is not null && stack is not empty{
as long as current is not null {
push the current node into the stack
keep looking left of current
}
since the stack is full, pop the last element in the stack and put it into current
push the current value into our empty results array
keep looking right of the tree 
}
return the results
}

Pseudocode Explained

With the inorder traversal method, we must create an empty stack and an empty results array as well. We need to see if the root is empty, if so we must return an empty array.

If the root is not empty, we can assign a current variable to the root which will be important for us in our while loops.

The way I went about it was to create two while loops:

1. ) While current is not null AND our stack length is not 0
2. ) while current is not null

For the second while loop, once the current node has a null child, we can push to the back, that current element into our stack. Initialize current as current.left to keep going left of the tree, we know that the children in the left are always less than the root.

For the first while loop, as long as our statements are true, we can now look into the stack and start to pop() elements from the back, initializing that element to our current variable. We then push the current value into our results to print out. Making sure that the right side is being touched through the iteration

Finally, we can return the results!

Diagram:

In-order Traversal

inorder traversal by Tushar Roy — Coding Made Simple

Post-order Traversal

Post-order traversal operates in a sort of backward direction. Meaning, it traverses first to the left and right children nodes, then its last stop is the root/(top) of the tree.

function postorderTraversal(root){
does root exist?
create empty stack array
create empty results array
push root into stack
while(stack is greater than 0){
from the stack, pop off the last element and into a current variable
unshift the current value into our results
any current children on left ? push that child into stack
any current children on right ? push that child into stack
}
return results
}

Pseudocode Explained

The great thing about the postorder traversal method is that it has a slight resemblance to the preorder traversal method. The only difference is that, in the while loop, as we pop() off the last element of the stack, we then push the current value to the front — using .unshift() — into our results array from left to right then to the root.

Post-order Traversal

postorder traversal by Tushar Roy — Coding Made Simple

Breadth-First Search (Level Order)

This is an algorithm for traversing or searching in a tree or graph data structure. It first starts at the root(top) of the tree, then explores all the neighboring nodes.

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

function levelorderTraversal(root){
check if the root is empty
initialize a results array
push our root into a queue array
while the queues' length is not empty{
initialize another empty array (subarray)
create a for loop to got through our tree leaf by leaf{
with every leaf touched, pop off the last and let that be the current node
push the current node into our subarray
if there is a leaf on the left of the current node, add to the front of our queue that left node leaf
if there is a leaf on the right of the current node, add to the front of our queue that right node leaf
}
when done push all of our subarray to our results
}
return those results
}

Pseudocode Explained

The Breadth-First Search algorithm was a challenge for me to understand. Knowing about queues does help you when tackling an algorithm that needs a place holder.

With that said, We do our usual checking of the root to see if it is empty or not. We then create a queue array variable to assign the root to.

With the way I learned, we create a while loop that contains an empty array variable called subarray. We then create a for loop:

1. we must initialize a currentNode variable to the last element popped off of our queue
2. Into our subarray variable, we now push() the element values from currentNode.
3. a. If our currentNode has left children we add to the front that currentNode element into our queue variable.
4. b. If our currentNode has right children we add to the front that currentNode element into our queue variable\

Once that is all done, we can now push all that is in our subarray variable into our results array variable. Which we, of course, must return at the end of the loops!

Note: This was honestly the hardest of the trees that I learned, with consistent youtube videos, documentations, eventually looking up the answer, I was very stumped on how to approach Breadth-First search! Apologies in advance if this section does not make complete sense, if you have a better way of solving something like this please don't hesitate to tell me in the comment section.

Breadth-First Search (Level Order)

breadth search first by mycodeschool

Resources

Explore - LeetCode

Breadth-first search

Tree traversal