Traverse binary tree in level order by spiral

Traverse binary tree in level order by spiral

Another puzzle is at stake, folks. This time it is binary tree related (not necessarily binary search tree as we are not interested in data relations but rather in binary tree structure). We need to traverse binary tree level by level (level is defined as set of all nodes at the same distance from root) in such a way that traversal direction within level changes from level to level thus forming a spiral. For example, consider binary tree below (it is rotated 90 degrees counter clockwise). Asterisk means NIL node. * 20 * 19 * 18 * 17 * 13 * 12 * 11 * 10 * 7 * 6 * 5 * 4 * 2 * Desired traversal for this tree will be: 10, 4, 11, 12, 6, 2, 5, 7, 19, 20, 17, 13, 18. Dissected into levels it looks like: 10 20, 17 13, 18 It may not be obvious how to approach the problem. We'll start with a well know problem of traversing binary tree level by level (also known as breadth first traversal ). It can be done using queue.

Read full article from Traverse binary tree in level order by spiral