Change the right pointer of every leaf node to the next leaf node in binary tree

Question

recently i saw a question on internet and want to know if there is more efficient solution possible than what i have done.

Queus : change the right pointer of every leaf node to the next leaf node in binary tree.
The leaves may not be at same level.

node of binary tree is of form of :

struct node  
{  
     struct node *left , *right ;  
     int key;  
};

I solved it using LEVEL ORDER TAVERSAL(BFS) on tree and finally got ALL the leaf nodes in a queue.
now connecting nodes is very easy :

while(queue is not empty)  
{
  currentnode = queue.pop();
 currentnode->right= queue.top();
}
 currentnode->right= NULL;// queue becomes empty on taking out last node

i use O(n) time , but extra space O(n). can it be done without taking less space or no space ?

Answer 1

I would suggest the following approach, of course it must be tested but I think it should work.

If you do a In-Order-Traversal of the binary tree you would find the nodes in the left-right order. Now, we can check if a node is a leaf, and if it's a leaf we have to do two things:

1. link the previous leaf to current leaf
2. update the current leaf as the previous

---

void inOrderTraversal(Node root, Node previous){
   if(root!=null){
      inOrderTraversal(root.left, previous);
      if(root.left==null && root.right==null){
         if(previous!=null)
            previous.right=root;
         previous=root;
      }
      inOrderTraversal(root.right, previous);
   }
}

In this way you have a better space complexity: O(1).

Answer 2

In your algorithm, instead of storing the leafs in the queue, simply make the right pointers of previous leaf point to the current leaf as you go.

lastLeaf->right = currLeaf;
lastLeaf = currLeaf;