Convert Binary Tree to Doubly linked list in level order

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:

The output will be a double linked list like this:

Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.
For traversing the tree, we'll use level / order traversal a.k.a breadth first search.

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)

#include<iostream>
#include<queue>
using namespace std;
struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};
struct Node* bt2DoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;
  queue nodeQueue;
  struct Node* head = root; //reference to head of the linked list
  struct Node* listIT = NULL; //current node being processed
  struct Node* prevNode = NULL; //previous node processed
  //initialize the stack
  nodeQueue.push(root);
  //convert to double linked list
  while (!nodeQueue.empty())
  {
    //process next node in stack
    prevNode = listIT;
    listIT = nodeQueue.front();
   
    nodeQueue.pop();
    //add left child to stack
    if (listIT->left != NULL)
      nodeQueue.push(listIT->left);
    //add right child to stack
    if (listIT->right != NULL)
      nodeQueue.push(listIT->right);
    //add current node to linked list
    if (prevNode != NULL)
      prevNode->right = listIT;
    listIT->left = prevNode;
  }
 
  //connect end node of list to null
  listIT->right = NULL;
  return head;
}

Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:

1. If the root node is null, we return null because the tree is empty.
2. If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
3. Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
4. We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
5. The while loop will run until no node left in queue to process. For each node in the queue, we do the following:
   
   prevNode = listIT gets reference to the last processed node because we are about to process a new node
   
   listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.
   
   nodeQueue.pop() removes the top node out of the queue.
   
   We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.
   
   Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.
   
   
6. When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

Read More

Reverse the doubly linked list

Problem

Reverse the doubly linked list

Input
10 - 8 - 4 - 2

Output
2 - 4 - 8 - 12

Solution

Method 1 - Reversing the prev and next references
Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next references  in all the nodes of the list and need to make head point to the last node of original list (which will be the first node in the reversed list).

void reverseDLL(Node head)
 {
    while(head!=null)
    {
       // Swapping the prev & next pointer of each node
       Node t = head.prev;
       head.prev = head.next;
       head.next = t;
 
       if(head.prev != null)
          head = head.prev;  // Move to the next node in original list
       else
          break;              // reached the end. so terminate
    }
 }

Time complexity - O(n)

Reference
http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/

Read More

Doubly linked list ADT

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two  fields, called links, that are references to the previous and to the next node in the sequence of nodes.

The beginning and ending nodes previous and next  links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items,  but in opposite sequential orders.

ADT

    class Node {
        E element;
        Node next;
        Node prev;
 
        public Node(E element, Node next, Node prev) {
            this.element = element;
            this.next = next;
            this.prev = prev;
        }
    }

Operations

• Insert
• Delete
• Update
• Find

Java usage

java.util.LinkedList is a doubly-linked list.


Reference

• http://java2novice.com/data-structures-in-java/linked-list/doubly-linked-list/

Read More

Bubble sort on double linked list

 Following can be the pseudocode:

public void bubbleSort() {
    boolean done = false;
    while (!done) {
        Node cur = head;
        done = true;
        while(cur != tail) {
            if (cur.getNext().getCount()>cur.getCount()) {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
}

Thanks.
Source : stackoverflow

Read More

Implementing doubly linked list using single pointer

http://chanduthedev.blogspot.in/2012/10/implementing-doubly-linked-list-using-single-pointer.html

http://chanduthedev.blogspot.in/2012/10/double-linked-list-using-single-pointer.html

Read More

Convert Binary Tree to Double Linked List in Zig-Zag Order

Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order.
Solution: let's first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level. For example, take a look at this tree:

A zig-zag level-order traversal creates the list 1, 2, 3, 5, 4. It doesn't matter which direction the root is printed because there is only one node. However, since the second level is printed left to right, 2 then 3, the third level is printed from right to left, 5 then 4.

Now we understand the question, let's figure out how to solve this problem. Well, the only tricky part is to traverse the tree in zig-zag order. The other part, adding nodes to a linked list, is easy.
We have already seen how to do zig zag order traversal here.

To solve this problem, we need two stacks. One stack stores nodes of levels that traversed from left to right. The other stores nodes of levels that traversed from right to left. The idea is to add the children of each node of the same level into a different stack than their parent. Thus, all children of the same level are in the same stack, separating one level from another. These children nodes are also pushed in the stack in the same direction with each other but opposite direction with their parents, so they can be traversed in the opposite direction to their parents. Moreover, as we traverse the tree, we add each node into a double linked list.

public static <T> DoubleLinkedList<T> 

bt2ZigZagDoubleLinkedList(BSTNode<T> root)
{
 if (root == null)
  return null;

 DoubleLinkedList<T> head = new DoubleLinkedList<T>();
 head.addHead(root.data);

 BSTNode<T> listIT = null;
 BSTNode<T> prevNode = null;

 Stack<BSTNode<T>> left2RightStack = 

new Stack<BSTNode<T>>();
 Stack<BSTNode<T>> right2LeftStack = 

new Stack<BSTNode<T>>();

 left2RightStack.push(root);

 while (!left2RightStack.empty())
 {
  //add nodes from left to right to the list
  while (!left2RightStack.empty())
  {
   //set previous node
   prevNode = listIT;

   //pop a node in left2RightStack and add it to list
   listIT = left2RightStack.peek(); 
   left2RightStack.pop();

 //add child nodes of the newly node in right to left direction
   if (listIT.left != null)
    right2LeftStack.push(listIT.left);

   if (listIT.right != null)
    right2LeftStack.push(listIT.right);

  //set left pointer of current node to the node in front of it
   listIT.left = prevNode; 

  //the previous node points to the current node in list
   if (prevNode != null)
    prevNode.right = listIT;
  }

 //add nodes from right to left to the list
  while (!right2LeftStack.empty())
  {
   prevNode = listIT;

   listIT = right2LeftStack.peek();

   right2LeftStack.pop();

   if(listIT.right != null)
    left2RightStack.push(listIT.right);

   if(listIT.left != null)
    left2RightStack.push(listIT.left);

   listIT.left = prevNode;

   if (prevNode != null)
    prevNode.right = listIT;
  }
 }

//connect linked the end node of list to null and the node in front of it
 listIT.right = null;
 listIT.left = prevNode;

 return head;
}

Read More

Double Linked List Structure

If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below.

Of course we need a pointer to some link in the doubly-linked list to access list elements. It is convenient for doubly-linked lists to use a list header, or head, that has the same structure as any other list item and is actually part of the list data structure. The picture below shows an empty and nonempty doubly-linked list. By following arrows it is easy to go from the list header to the first and last list element, respectively.

Insertion and removal of an element in a doubly-linked list is in this implementation rather easy. In the picture below we illustrate the pointer changes for a removal of a list item (old pointers have been drawn solid and new pointers are dashed arrows). We first locate the previous list item using the previous field. We make the next field of this list item point to the item following the one in cursor position pos. Then we make the previous field of this following item point to the item preceding the one in the cursor position pos. The list item pointed to by the cursor becomes useless and should be automatically garbage collected.

Implementing the double list items

Double List Node

package com.vaani.ds.doublelist;

final class DoubleListNode {
    Object obj;
    DoubleListNode previous, next;

    public DoubleListNode(Object obj) {
        this(null, obj, null);
    }

    public DoubleListNode(DoubleListNode previous, 

                                   Object obj, DoubleListNode next) {
        this.previous = previous;
        this.obj = obj;
        this.next = next;
    }
}

A class definition with only two constructor methods. The keyword final ensures that this class has no subclasses nor that a user can derive a class from this one.

DoubleLinkedList.java

public class DoubleLinkedList <E>{   
    DoubleListNode<E> head;
    private DoubleListNode<E> tail;
    private int length=0;
    /*
     * creates an empty list
     */
    public DoubleLinkedList() {
        //        head = new DoubleListNode<E>(null);
        //        head.next = head.prev = head;
        head.setPrev(null);
        head.setNext(tail);
        tail.setPrev(head);
        tail.setNext(null);
    }

    public DoubleListNode<E> get(int index) 
                                throws IndexOutOfBoundsException {
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException();
        } else {
            DoubleListNode<E> cursor = head;
            for (int i = 0; i < index; i++) {
                cursor = cursor.getNext();
            }
            return cursor;
        }
    }

    public E remove(int index) throws IndexOutOfBoundsException {
        if (index == 0) {
            throw new IndexOutOfBoundsException();
        } else {
            DoubleListNode<E> result = get(index);
            result.getNext().setPrev(result.getPrev());
            result.getPrev().setNext(result.getNext());
            length--;
            return result.getValue();
        }
    }
    /*
     * remove all elements in the list
     */
    public final  void clear() {
        head.next = head.prev = head;
    }

    /*
     * returns true if this container is empty.
     */
    public final boolean isEmpty() {
        return head.next == head;
    }

    public int size() {
        return length;
    }


    public String toString() {
        StringBuffer result = new StringBuffer();
        result.append("(head) - ");
        DoubleListNode<E> temp = head;
        while (temp.getNext() != tail) {
            temp = temp.getNext();
            result.append(temp.getValue() + " - ");
        }
        result.append("(tail)");
        return result.toString();
    }

    public void add(int index, E value) 
                                throws IndexOutOfBoundsException {
        DoubleListNode<E> cursor = get(index);
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }

    public void addHead(E value) {
        DoubleListNode<E> cursor = head;
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }

    public void addTail(E value) {
        DoubleListNode<E> cursor = tail.getPrev();
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }


    /*
     * Return an iterator positioned at the head.
     */
    public final DoubleListIterator head() {
        return new DoubleListIterator(this, head);
    }


}

Read More

Vertical Sum of a Binary Tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-vertical-sum-in-binary-tree/.

Question : Find vertical sum of given binary tree.

Example:

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

The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7

To see more clearer picture :

Verticals of a Binary Tree

To understand what's same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD) , then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.

Also, HD can be thought of as difference between right moves (r) - left moves (l) . So, for
node 1, r=0,l=0, HD=0
For node 2, l=1,r=0 , therefore HD=-1
For node 3, l=0,r=1, therefore HD =1
For node 4, r=0, l=2 therefore HD = -2
Fore node 5, r=1, l=1, therefore HD = 0

Solution 1: Using the hashmap

Define a dictionary (hash map) from HD to sum. And for each node you visit add its value to the dictionary key - this is a O(n) solution.
We can do an inorder traversal and hash the column. We call Traverse(root, 0) which means the root is at column 0. As we are doing our traversal, we can hash the column and increase its value by T.data. A rough sketch of my function looks like this -

Traverse(Tree T, int hd)
{
  if(T==NULL) return;
  Traverse(T.left, column-1);
  Hash(hd) += T.data;
  Traverse(T.right, column+1);
}

To begin with, Traverse will be called like

Traverse(root,0) 

hd = 0 for root, so we passed 0.So, while calling left node, we decrease hd and opp for right node.

Here is the code in Java:

private void printVerticalSum(TreeNode root) {

    // base case
    if (root == null) { return; }

    // Creates an empty hashMap hM
    HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

    // Calls the VerticalSumUtil() to store the vertical sum values in hM
    printVerticalSumUtil(root, 0, hM);

    // Prints the values stored by VerticalSumUtil()
    if (hM != null) {
        System.out.println(hM.entrySet());
    }
}

// Traverses the tree in Inoorder form and builds a hashMap hM that
// contains the vertical sum
private void printVerticalSumUtil(TreeNode root, int hD,
                                      HashMap<Integer, Integer> hM) {

    // base case
    if (root == null) {  return; }

    // Store the values in hM for left subtree
    VerticalSumUtil(root.left(), hD - 1, hM);

    // Update vertical sum for hD of this node
    int prevSum = (hM.get(hD) == null) ? 0 : hM.get(hD);
    hM.put(hD, prevSum + root.key());

    // Store the values in hM for right subtree
    VerticalSumUtil(root.right(), hD + 1, hM);
}

Solution2 : Using doubly link list

Here is the solution for doubly link list
Basic algo

1. Start with the root node and empty double list listNode
2. Add the value of the rootNode to the current listNode
3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
4. Similarly for right node, pass listNode.right and root.right

Pseudocode

node { sum = 0; node *next=NULL; node *prev=NULL; } 

printVerticalSum(TreeNode root)
{
   if(root==null)
       return -1;
    allocate node doubleLinkList //initialize,
    printVerticalSumUtil(root, doubleLinkList); 
    //write the function to print double linked list
    System.out.println(doubleLinkList.toString())
}

printVerticalSumUtil(TreeNode root, ListNode listNode)
{
  if(root==NULL) return;
 
  if(root.left!=NULL)
    if(listNode.prev!=NULL)
      listNode.prev.data += root.data;
    else
      ListNode t = new ListNode(root.data);
      t.next=listNode; 
      listNode.prev = t;
    findVerticalSum(root.left, listNode.prev)
 
  if(root.right!=NULL)
    if(listNode.next!=NULL)
      listNode.next.data += root.data;
    else
      ListNode t = new ListNode(root.data);
      t.prev=listNode; 
      listNode.next = t;
    findVerticalSum(root.right, listNode.next)
}

Time complexity is O(n) in both the methods.

Thanks

Reference

• http://stackoverflow.com/questions/14485255/vertical-sum-in-a-given-binary-tree

Read More

How to reverse a doubly linked list ?

I talked about how to reverse a singly linked list earlier. That was slightly tricky to understand.

Reversing a doubly linked list is relatively easy. The logic is : You need to keep on changing the next and previous pointers as you traverse the entire list. Here is the code snippet in Java :

public void reverse()
{
    if (first == null) 
          return;

    DoubleNode previous = first;
    DoubleNode current = first.next;
    first.next = null;
    while (current != null)
    {
            DoubleNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
    }
    first = previous;
}

Read More

Function to add node to double link list

2 struct pointers (Double link list)
typedef struct node
{
  int value;
  struct node *next;
  struct node *prev;
}mynode ;

// Function to add a node
void add_node(struct node **head, int value)
{
  mynode *temp, *cur;
  temp = (mynode *)malloc(sizeof(mynode));
  temp->next=NULL;
  temp->prev=NULL;

  if(*head == NULL)
  {
     *head=temp;
     temp->value=value;
  }
  else
  {
   for(cur=*head;cur->next!=NULL;cur=cur->next);
   cur->next=temp;
   temp->prev=cur;
   temp->value=value;
  }
}

Read More