Depth First Search Binary Tree
Tags: javascript, python, algorithms, programming
Published: 2021-03-11 10:15:48

## Depth-first search
This approach involves backtracking for traversal and the deepest node is visited first and then backtracks up to the parent. There are three types of DFS traversal:-

* Preorder
* Inorder
* postorder

### PreOrder
In pre-order traversal of a binary tree, we first traverse the root, then the left subtree, and then finally the right subtree. We do this recursively to benefit from the fact that left and right subtrees are also trees.

The steps to follow.
1. Create a function traverse and call it on the root
2. call traverse on the left sub-tree.
3. call traverse on the right sub-tree.

### InOrder
In the In-order traversal of a binary tree, we first traverse the left subtree, then traverse the root, and then finally the right subtree. We do this recursively to benefit from the fact that left and right subtrees are also trees.

The steps to follow.
1. call traverse on the left sub-tree.
2. Create a function traverse and call it on the root
3. call traverse on the right sub-tree.


### PostOrder
In post-order traversal of a binary tree, we first traverse the left subtree, then the right subtree, and then finally the root. We do this recursively to benefit from the fact that left and right subtrees are also trees.


JavaScript implementation:-
```js
class Node{
    constructor(val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST{
    constructor(){
        this.root = null;
    }

    insert(val){
        let newNode = new Node(val);
        if(!this.root){
            this.root = newNode;
        }else{
            let current = this.root;
            while(true){
                if(val < current.val){
                    if(current.left === null){
                        current.left = newNode;
                        return this
                    }else{
                        current = current.left;
                    }
                }else{
                    if(current.right === null){
                        current.right = newNode;
                        return this
                    }else{
                        current = current.right
                    }
                }
            }

        }

    }
    find(val){
        let current  = this.root;
        let found = false;
        while(current && !found){
            if(val < current.val){
                if(current.val === val){
                    found = true;
                    return current;
                }else{
                    current = current.left;
                }
            }else{
                if(current.val === val){
                    found = true;
                    return current;
                }else{
                    current = current.right;
                }
            }
        }
        return 'not found'
    }

   
    DFSPreOrder(){
        let data=[];
        function traverse(node){
            data.push(node.val);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;

    } 

        DFSPostOrder(){
        let data=[];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.val);
        }
        traverse(this.root);
        return data;

    }

       DFSInOrder(){
        let data=[];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.val);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;

    }
}

```

Python implementation:-

```py
class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        
        
class BST:
    def __init__(self):
        self.root= None
        
    def insert(self, val):
         newNode = Node(val)
         if self.root == None:
             self.root= newNode
         else:
             current = self.root
             while True:
                 if val< current.val:
                     if current.left == None:
                         current.left = newNode
                         return self
                     else:
                         current= current.left 
                 else:
                     if(current.right == None):
                         current.right = newNode
                         return self
                     else:
                         current = current.right
                           
    def  find(self, val):          
                current= self.root
                found = False
                while current and not found:
                    if val < current.val:
                        current = current.left
                    elif val > current.val:
                        current= current.right
                    else:
                        found = True
                if(not found): return "not found"
                return current
    
    def dfspreorder(self):
        data =[]
        
        def traverse(node):
            data.append(node.val)
            if(node.left): traverse(node.left)
            if(node.right): traverse(node.right)
        traverse(self.root)         
        return data
    
    
    def dfsInorder(self):
        data =[]
        
        def traverse(node):
            if(node.left): traverse(node.left)
            data.append(node.val)
            if(node.right): traverse(node.right)
        traverse(self.root)         
        return data
    
    
    def dfspostorder(self):
        data =[]
        
        def traverse(node):
            if(node.left): traverse(node.left)
            if(node.right): traverse(node.right)
            data.append(node.val)
        traverse(self.root)         
        return data

        
bst = BST()
bst.insert(100)
bst.insert(200)
bst.insert(150)
bst.insert(175)
bst.insert(160)
bst.insert(180)
bst.insert(75)
bst.insert(50)
bst.insert(65)
bst.insert(40)
bst.insert(55)
bst.insert(20)

print(bst.bfs())
print(bst.dfspreorder())


```