Level Order Traversal Of A Tree In C++
Level Order Traversal Of A Tree
A tree can be traversed using level order and depth first order. In level order traversal, we move level by level that is we visit all the nodes in the same level then move onto the next level. Level order traversal can be achieved using recursion or queue.
- If the root is NULL, return.
- Otherwise push the root in queue.
- Print the node’s data and add its left and right child.
- Pop the node from the queue.
- Repeat until the queue is empty.
Why Queue is better to traverse than Recursion?
- Queues improves the time complexity because recursion gives the time complexity of O(2^n) in the worst case, whereas queue gives time complexity of O(n).
- Height of the tree is first calculated to print level order but this is not required in queue.
- Implementation is shorter in queues.
10 20 30 40 50
For Level Order Travesal