Depth First Search Binary Tree

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

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

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())