Code_Regina

Posted on

# Tree Traversal

``````                   -Intro to Tree Traversal
-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

Steps to take for breadth first search

1. Create a queue (can be an array) and a variable to store the values of nodes visited.
2. Place the root node in the queue.
3. 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

1. Create a variable to store the values of nodes visited.
2. Store the root of the BST in a variable called current.
3. 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

1. Create a variable to store the values of nodes visited.
2. Store the root of the BST in a variable called current.
3. 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

1. Create a variable to store the values of nodes visited.
2. Store the root of the BST in a variable called current.
3. 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;
}
}

``````