Monday, July 30, 2018

Binary tree - DFS and BFS

 Depth first search

In depth first search (dfs) you start with a root node and keep on traversing left node (or right node) until you reach leaf node, then backtrack for other side.


There are two ways in which you can implement dfs search -

  • Recursive
  • Iterative using stack


Node.java


DFSSearch.java

Output - 

Depth first search - using Recursion
50 25 20 10 22 30 27 40 75 70 60 74 90 80 93 
Depth first search - using Stack
50 25 20 10 22 30 27 40 75 70 60 74 90 80 93 


Breadth first search

In breadth first search (bfs) you start with a root noode and then visit its left node (A) and right node (B), continue visiting left and right node of A and B. Repeat this process till leaf node.


This can be implemented using Queue

BFSSearch.java

Output -

Breath first search - 

50 25 75 20 30 70 90 10 22 27 40 60 74 80 93 

No comments:

Post a Comment