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:-
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())
Top comments (0)