Skip to main content

Posts

Showing posts with the label bfs

BFS of binary tree

Question : Write a function for BFS traversal of a binary tree. Bread first traversal (also called level order traversal) is a traversal method where you visit the siblings of a node before you visit its descendants. The other method of traversal is called depth first traversal(DFS) where you visit the descendants of a node before you visit its siblings. In-order, pre-order and post-order are all DFS traversal methods. In BFS, first you visit all the nodes at level 0, then you visit all the nodes at level 1, then you visit nodes at level 2 etc. For the diagram shown above, the BFS output should be 8 3 10 1 6 14  4 7 13  ( there is no newline between levels) To write a code for BFS, we need to take the help of another data structure - a queue. To start with we insert this root to the queue. Then as long as queue is not empty, we remove a node from the queue, visit this node (display its value) and enqueue its both child nodes.  Here is C function f...