-Intro to Tree Traversal
-Breadth First Search
-Depth First PreOrder
-Depth First PostOrder
-Depth First InOrder
Intro to Tree Traversal
There are two ways for tree traversal.
Breadth first search and depth first search
Breadth First Search
Steps to take for breadth first search
- Create a queue (can be an array) and a variable to store the values of nodes visited.
- Place the root node in the queue.
- Loop as long as there is anything in the queue. -Dequeue a node from the queue and push the value of the node into the variable that stores the node. -If there is a left property on the node then dequeue add it to the queue. -If there is a right property on the node then dequeue - add it to the queue. -return the variable that stores the value.
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
var newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}
var current = this.root;
while(true){
if(value === current.value) return undefined;
if(value < current.value){
if(current.left === null){
current.left = newNode;
return this;
}
current = current.left;
} else {
if(current.right === null){
current.right = newNode;
return this;
}
current = current.right;
}
}
}
find(value){
if(this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
found = true;
}
}
if(!found) return undefined;
return current;
}
contains(value){
if(this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
return true;
}
}
return false;
}
BFS(){
var node = this.root,
data = [],
queue = [];
queue.push(node);
while(queue.length){
node = queue.shift();
data.push(node.value);
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data;
}
}
Depth First PreOrder
Steps to take for Depth first preorder search
- Create a variable to store the values of nodes visited.
- Store the root of the BST in a variable called current.
- Write a helper function which accepts a node. -Push the value of the node to the variable that stores the values. -If the node has a left property, call the helper function with the left property on the node. -If the node has a right property, call the helper function with the right property on the node. Invoke the helper function with the current variable.
DFSPreOrder(){
var data = [];
function traverse(node){
data.push(node.value);
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
Depth First PostOrder
Steps to take for Depth first postorder search
- Create a variable to store the values of nodes visited.
- Store the root of the BST in a variable called current.
- Write a helper function which accepts a node. -Push the value of the node to the variable that stores the values. -If the node has a left property, call the helper function with the left property on the node. -If the node has a right property, call the helper function with the right property on the node. Invoke the helper function with the current variable.
DFSPostOrder(){
var data = [];
function traverse(node){
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
data.push(node.value);
}
traverse(this.root);
return data;
}
Depth First InOrder
Steps to take for Depth first inorder search
- Create a variable to store the values of nodes visited.
- Store the root of the BST in a variable called current.
- Write a helper function which accepts a node. -Push the value of the node to the variable that stores the values. -If the node has a left property, call the helper function with the left property on the node. -If the node has a right property, call the helper function with the right property on the node. Invoke the helper function with the current variable.
DFSInOrder(){
var data = [];
function traverse(node){
if(node.left) traverse(node.left);
data.push(node.value);
if(node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
}
Top comments (0)