Your Web News in One Place

An Interest In:

Web News this Week

Search Archive

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
March 11, 2021 10:15 am GMT

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 = Noneclass 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 databst = 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())

Original Link: https://dev.to/edwardcashmere/depth-first-search-binary-tree-1o7c

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To