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 p…


This content originally appeared on DEV Community and was authored by Edwin

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



This content originally appeared on DEV Community and was authored by Edwin


Print Share Comment Cite Upload Translate Updates
APA

Edwin | Sciencx (2021-03-11T10:15:48+00:00) Depth First Search Binary Tree. Retrieved from https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/

MLA
" » Depth First Search Binary Tree." Edwin | Sciencx - Thursday March 11, 2021, https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/
HARVARD
Edwin | Sciencx Thursday March 11, 2021 » Depth First Search Binary Tree., viewed ,<https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/>
VANCOUVER
Edwin | Sciencx - » Depth First Search Binary Tree. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/
CHICAGO
" » Depth First Search Binary Tree." Edwin | Sciencx - Accessed . https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/
IEEE
" » Depth First Search Binary Tree." Edwin | Sciencx [Online]. Available: https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/. [Accessed: ]
rf:citation
» Depth First Search Binary Tree | Edwin | Sciencx | https://www.scien.cx/2021/03/11/depth-first-search-binary-tree/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.