Tree Traversal
Tags: webdev
Published: 2021-10-31 17:47:00

---
title: Tree Traversal
published: true
description: 
tags: webdev
//cover_image: https://direct_url_to_image.jpg
---

                       -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 
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. 

```javascript 

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. 

```javascript 

 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. 




```javascript 

    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. 



```javascript 
    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;
    }
}

```