Can anyone suggest an algorithm to traverse a binary tree level by level starting from root?
2 Answers
That's done by breadth-first searching your tree:
- Create a queue of tree nodes
- Enqueue the tree root
- While the queue is not empty, repeat the following:
- Dequeue a node, and print its content
- Enqueue the left sub-node of the current node
- Enqueue the right sub-node of the current node
When you follow this algorithm, all nodes from level K will be printed prior to printing the first node from level K+1, so the tree will be printed level-by-level.
answered Apr 23, 2013 at 23:27
Sergey Kalinichenko
729k85 gold badges1.2k silver badges1.6k bronze badges
1 Comment
G. Bach
Just thought I'd add that this obviously generalizes to k-ary ordered as well as general and thus unordered trees.
You can perform this kind of traversal using a queue. From the root node push its children to the end of a queue, then while the queue is not empty pop an item from the top of the queue and add its children to the end of the queue. Processing each node where appropriate.
This is essentially a Breadth First Traversal.
