How to swap adjacent node pairs in the same level in a binary tree

**aakashjsr** · Aug 30 '15, 06:45 AM

Please help me with developing an algorithm to swap adjacent pairs of nodes in the same level of the binary tree.I have a solution which takes a space complexity of O(n) but I need to figure out a better algorithm.

example

Code:

                        1
                      /   \
                     2     3
                   /  \     \
                  4   5      6
                 /            \
                7              8

should become

                        1
                      /   \
                     3     2
                   /  \     \
                  5   4      6
                 /            \
                8              7