A complete binary tree is a binary, which is completely filled, with the possible exception of the bottom level, which is filled from left and right.

The correct solution is to do an in-order traversal of the tree. keeping track of the node and the level you're on. Roughly: q.EnQueue(head, level = 1) lastlevel = 0 lastnode = null While (!q.IsEmpty()) node, level = q.DeQueue() if (level == lastlevel) lastnode.right = node lastnode = node lastlevel = level q.EnQueue(node.left, level + 1) q.EnQueue(node.right, level + 1) end while

Basically approach this using breadth first search. However after you find your next level, keep track of the prev node, and assign prev node's sibling to the current node. Just like assigning next pointers in a linked list.