Posted onMar 11, 2021

Depth First Search Binary Tree

#javascript #python #algorithms #programming

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.

Create a function traverse and call it on the root
call traverse on the left sub-tree.
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.

call traverse on the left sub-tree.
Create a function traverse and call it on the root
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:-

classNode{constructor(val){this.val=val;this.left=null;this.right=null;}}classBST{constructor(){this.root=null;}insert(val){letnewNode=newNode(val);if(!this.root){this.root=newNode;}else{letcurrent=this.root;while(true){if(val<current.val){if(current.left===null){current.left=newNode;returnthis}else{current=current.left;}}else{if(current.right===null){current.right=newNode;returnthis}else{current=current.right}}}}}find(val){letcurrent=this.root;letfound=false;while(current&&!found){if(val<current.val){if(current.val===val){found=true;returncurrent;}else{current=current.left;}}else{if(current.val===val){found=true;returncurrent;}else{current=current.right;}}}return'not found'}DFSPreOrder(){letdata=[];functiontraverse(node){data.push(node.val);if(node.left)traverse(node.left);if(node.right)traverse(node.right);}traverse(this.root);returndata;}DFSPostOrder(){letdata=[];functiontraverse(node){if(node.left)traverse(node.left);if(node.right)traverse(node.right);data.push(node.val);}traverse(this.root);returndata;}DFSInOrder(){letdata=[];functiontraverse(node){if(node.left)traverse(node.left);data.push(node.val);if(node.right)traverse(node.right);}traverse(this.root);returndata;}}

Python implementation:-

classNode:def__init__(self,val):self.val=valself.left=Noneself.right=NoneclassBST:def__init__(self):self.root=Nonedefinsert(self,val):newNode=Node(val)ifself.root==None:self.root=newNodeelse:current=self.rootwhileTrue:ifval<current.val:ifcurrent.left==None:current.left=newNodereturnselfelse:current=current.leftelse:if(current.right==None):current.right=newNodereturnselfelse:current=current.rightdeffind(self,val):current=self.rootfound=Falsewhilecurrentandnotfound:ifval<current.val:current=current.leftelifval>current.val:current=current.rightelse:found=Trueif(notfound):return"not found"returncurrentdefdfspreorder(self):data=[]deftraverse(node):data.append(node.val)if(node.left):traverse(node.left)if(node.right):traverse(node.right)traverse(self.root)returndatadefdfsInorder(self):data=[]deftraverse(node):if(node.left):traverse(node.left)data.append(node.val)if(node.right):traverse(node.right)traverse(self.root)returndatadefdfspostorder(self):data=[]deftraverse(node):if(node.left):traverse(node.left)if(node.right):traverse(node.right)data.append(node.val)traverse(self.root)returndatabst=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())