Edwin

Posted on

# 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;
}
}
}
}

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
if val < current.val:
current = current.left
elif val > current.val:
current= current.right
else:
found = True
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())

``````