BINARY SEARCH TREES: TRAVERSALS
I’m continuing my learning of the Binary Search Trees, so this post contains notes that I took on Traversals in the Binary Search Tree.
BST are beneficial when you need to access and process large amounts of ordered data very quickly, at the expense of some memory overhead.
Depth First Search (DFS) searches branch by branch, there are three different types of DFS.
The three types of DFS are IN-ORDER, PRE -ORDER and POST-ORDER
Breadth First Search (BFS) searches level by level.
1. INORDER
a. Left Sub Tree
b. Print Node
c. Right Sub Tree
2. PREORDER
a. Print Node
b. Left Sub Tree
c. Right Sub Tree
3. POSTORDER
a. Left Sub Tree
b. Right Sub Tree
c. Print Node
BINARY SEARCH TREES: TRAVERSALS — INORDER
LPR
_______50_______
/ \
LPR LPR
__25__ __75_
/ \ / \
LPR LPR LPR LPR
15 35 65 85
When using INORDER, each node has LPR written over it.
L = Left
P = Print
R = Right
Always start at the root node.
OUTPUT: 15, 25, 35, 50, 65, 75, 85
INORDER outputted in ascending order.
BINARY SEARCH TREES: TRAVERSALS — PREODER
PLR
_______50_______
/ \
PLR PLR
__25__ __75_
/ \ / \
PLR PLR PLR PLR
15 35 65 85
When using PREORDER, each node has PLR written over it.
P = Print
L = Left
R = Right
Always start at the root node.
OUTPUT: 50, 25, 15, 35, 75, 65, 85
BINARY SEARCH TREES: TRAVERSALS — PREODER
LRP
_______50_______
/ \
LRP LRP
__25__ __75_
/ \ / \
LRP LRP LRP LRP
15 35 65 85
When using POSTORDER, each node has LRP written over it.
L = Left
R = Right
P = Print
Always start at the root node.
OUTPUT: 15, 35, 25, 65, 85, 75, 50
BINARY SEARCH TREES: TRAVERSALS — INORDER, PREORDER, POSTORDER
There will be two methods
1. in the BTS class — has no params and will be making the initial call.
2. in the node class.
1. INORDER
a. Left Sub Tree
b. Print Node
c. Right Sub Tree
class BTS {
inorder(){
if(this.root)
// if there is a root node, then we can continue with the INORDER process.
this.root.inorder(this.order)
// if the tree is not empty, then we invoke the inorder method within the Node class, passing in the root node as the starting point.
}
}
class Node {
inorder(currentNode){
if(currentNode){
// if there is a current node, then we can do the following steps:
this.inorder(currentNode.left);
// traverse the left subtree and recursively invoke the inorder method to go left, the left child is passed in.
console.log(currentNode.data);
// print the data at the currentNode
this.inorder(currentNode.right);
// traverse the right subtree and recursively invoke the inorder method to go right, the right child is passed in.
}
}
}
2. PREORDER
a. Print Node
b. Left Sub Tree
c. Right Sub Tree
class BTS{
preorder(){
if(this.root)
// if there is a root node, then we can continue with the PREORDER process.
this.root.preorder(this.order)
// if the tree is not empty, then we invoke the preorder method within the Node class, passing in the root node as the starting point.
}
}
class Node {
preorder(currentNode) {
if(currentNode){
// if there is a current node, then we can do the following steps:
console.log(currentNode.data);
// print the data at the currentNode
this.preorder(currentNode.left);
// traverse the left subtree and recursively invoke the preorder method to go left, the left child is passed in.
this.preorder(currentNode.right);
// traverse the right subtree and recursively invoke the preorder method to go right, the right child is passed in.
}
}
}
3. POSTORDER
a. Left Sub Tree
b. Right Sub Tree
c. Print Node
class BTS{
postorder(){
if(this.root)
// if there is a root node, then we can continue with the POSTORDER process.
this.root.postorder(this.order)
// if the tree is not empty, then we invoke the postorder method within the Node class, passing in the root node as the starting point.
}
}
class Node {
postorder(currentOrder){
if(currentNode){
// if there is a current node, then we can do the following steps:
this.postorder(currentNode.left);
// traverse the left subtree and recursively invoke the postorder method to go left, the left child is passed in.
this.postorder(currentNode.right);
// traverse the right subtree and recursively invoke the postorder method to go right, the right child is passed in.
console.log(currentNode.data);
// print the data at the currentNode
}
}
}
_______50_______
/ \
__25__ __75_
/ \ / \
15 35 65 85
/ \ / \ / \ / \
null null null null null null null null
In conclusion, BST are beneficial when you need to access and process large amounts of ordered data very quickly, at the expense of some memory overhead.
Depth First Search (DFS) searches branch by branch, there are three different types of DFS.
The three types of DFS are IN-ORDER, PRE -ORDER and POST-ORDER
Breadth First Search (BFS) searches level by level.
For now, this is the last post on the Binary Search Tree.
I will move on to learning about other Data Structures.