Coding Recipies

12 Apr 2014

Trees: Connect Right Peers

Problem Statement:
Connect nodes to their peers on right at each level.

Given Binary Tree:

Output Binary Tree should be:

Solution:
Download Source Code

This question was asked to me in one of the interviews(Akamai), for which i initially gave Iterative BFS solution, after some cross-questioning i came up with the recursive one.
The solution i have discussed here is very intuitive as we need to connect nodes of the same level, so we would adopt Iterative BFS approach for the solving the problem. The problem can also be solved by recursive approach, which i will discuss in some other post.

Implementation of connect to right peers:

private Queue<Node> queue = new LinkedList<Node>();
 /**
  * Connect Nodes to their peers on the right at the same level,
  * Performing BFS on the given tree and connecting peers
  */
 public void connect(Node root) {
  queue.add(root);
  queue.add(null);
  while (!queue.isEmpty()) 
  {
   Node poped = queue.poll();
   if (poped == null) 
   {
    if (queue.isEmpty()) // if last node , terminate
     continue;
    queue.add(null);
   } 
   else 
   {
    poped.peer = queue.peek();

    if (poped.left != null)
     queue.add(poped.left);
    if (poped.right != null)
     queue.add(poped.right);
   }
  }
 }

Display Tree:
Implementation of the displaying the tree after the peers are connected.

 /**
  * Print the modified Tree,
  * We are using left child of every level and then printing its peers
  */
 private static int maxLevel = 0;
 public void display(Node root, int level) {
  if (root == null)
   return;

  if (maxLevel < level) {
   Node temp = root;
   while (temp != null) {
    System.out.print(temp + "--->  ");
    temp = temp.peer;
   }
   System.out.println();
   maxLevel = level;
  }

  display(root.left, level + 1);
  display(root.right, level + 1);
 }

Please post your suggestions and comments.
Happy Coding !! :)

27 Jan 2014

Linked List : Pair Swapping(Iterative)

Problem Statement:
Iterative Pair swap the elements of the Linked List

Source Code
Solution:

We require minimum of three pointers. I have used 'temp' for moving forward. 'back' pointer points to the next of 'front' pointer.'front' is the leading pointer which then later connects to 'back'.

Below is the Iterative Implementation:

/**
  * Iterative Subroutine to swap pairs of nodes of linked list
  * @return new Head of the linked list
  */
 public Node pairSwap(Node head){
  Node temp=head;
  head=head.next; //new head
  
  Node front,back;
  while(temp!=null && temp.next!=null)
  {
   back=temp;
   front=temp.next;
   
   back.next=front.next;
   front.next=back;
   
   if(temp.next!=null)
    temp=temp.next;
   if(temp.next!=null)
    back.next=temp.next;
  }
  return head;
 }

Please comment and post if any better or efficient approach available may be with lesser pointers.
Happy Coding !! :)

Linked List: Pair Swapping (Recursive)

Problem Statement:
Perform pair-wise swapping on the given linked list using recursion.

Source Code Link
Solution:

Below is the subroutine implementation for achieving the resultant linked list

/**
  * Recursive Subroutine to swap pairs of nodes of linked list
  * @return new Head of the linked list
  */
 public Node pairSwap(Node head){
  Node curr=head;
  Node front=null;
 
  if(curr!=null && curr.next!=null){
   front=curr.next;
   curr.next = pairSwap(front.next);
   front.next=curr;
  }
  return (front!=null) ? front : curr;
 }

Please comment and post your suggestion or any modification to the above code.
Happy Coding !!:)