Tree Data Structures

Family Tree — FirstCry Parenting

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 stackwhile(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
}
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 currentpush the current value into our empty results array
keep looking right of the tree
}
return the results
}
  1. ) While current is not null AND our stack length is not 0
  2. ) while current is not null
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 stackwhile(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}
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.

function levelorderTraversal(root){check if the root is emptyinitialize a results arraypush our root into a queue arraywhile 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 subarrayif 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
}
  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\
Breadth-First Search (Level Order)
breadth search first by mycodeschool

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store