<body><script type="text/javascript"> function setAttributeOnload(object, attribute, val) { if(window.addEventListener) { window.addEventListener('load', function(){ object[attribute] = val; }, false); } else { window.attachEvent('onload', function(){ object[attribute] = val; }); } } </script> <div id="navbar-iframe-container"></div> <script type="text/javascript" src="https://apis.google.com/js/platform.js"></script> <script type="text/javascript"> gapi.load("gapi.iframes:gapi.iframes.style.bubble", function() { if (gapi.iframes && gapi.iframes.getContext) { gapi.iframes.getContext().openChild({ url: 'https://www.blogger.com/navbar.g?targetBlogID\x3d8334277\x26blogName\x3dSriram\x27s+Blog\x26publishMode\x3dPUBLISH_MODE_BLOGSPOT\x26navbarType\x3dBLUE\x26layoutType\x3dCLASSIC\x26searchRoot\x3dhttps://metallicatony.blogspot.com/search\x26blogLocale\x3den\x26v\x3d2\x26homepageUrl\x3dhttp://metallicatony.blogspot.com/\x26vt\x3d6147907796332168684', where: document.getElementById("navbar-iframe-container"), id: "navbar-iframe" }); } }); </script>

Friday, December 20, 2013

Binary Tree Traversals

Binary tree is a special case of a tree in which there are no more than 2 children for any node. The children are called left and right nodes respectively based on the fact whether they are located on the left or right side of the parent node. Binary trees are extensively used in software engineering because it just takes O(log n) for doing most of the day to day operations – insert, update, delete and search. Traversal algorithms are very important concepts in binary trees because if you want to do any type of operation on a binary tree then as a first step, the tree needs to be traversed to find the nodes on which the desired operation need to be performed. The three widely used binary tree traversal algorithms are

1) Preorder traversal
Processing order of the nodes are – parent, all its left descendants and then the right descendants. In other words, Parent is processed before left sub-tree and right sub-tree are processed.

2) Inorder traversal
Processing order of the nodes are – all left descendants, parent and then the right descendants. In other words, left sub-tree is processed before parent and right sub-tree are processed.

3) Postorder traversal
Processing order of the nodes are – all left descendants, right descendants and then finally the parent descendants. In other words, all the children are processed before the parent is processed.

For the impatient code readers, the entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms.

Recursive Solution
A recursive solution best suits the situation where there is a bigger problem that can be broken down into smaller and similar sub problems and so the same solution can be applied over the sub-problems. It is imperative to have a base case after which the solution should start winding up. Recursion can be best understood when the whole process can be visualized with a stack.

Iterative Solution
An iterative solution best suits the situation where there is a bigger problem that can be broken down into smaller problems and every such smaller problem is iteratively solved one after another. There is no connection between an iteration and its successive iterations. As in the case of recursion, an iteration does not pause or wait until all the sub-iterations are complete. And that’s why we need an additional tool(aka data structure) so that we can adapt an iterative solution for tree-traversals. A stack is needed in an iterative solution so that it can be used to temporarily store the nodes in the needed order and then apply the solution or process the node that comes out of the stack.

Preorder traversal
Recursive solution is simple and self-explanatory.

public void preOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  System.out.println(node);
  if (node.getLeft() != null) {
   preOrderTraversalIterative(node.getLeft());
  }
  if (node.getRight() != null) {
   preOrderTraversalIterative(node.getRight());
  }
 }

Iterative solution for any traversal needs at least a stack. Preorder traversal is the simplest among all the traversal iterative algorithms. To start with, the root node is added to stack. From there on, we navigate deep into the left-most sub-tree. And while doing so, we keep processing the node that we are navigating through and we keep adding the right child of the node (if exists) to the stack. The left child is added too but it is popped out in the next iteration, and that’s how we navigate down the tree. While we pop out the nodes from the stack, we go over the same process – navigate, process and add the right child to stack if it exists.

public void preOrderTraversalIterative(Node node) {
Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  
  while (!stack.isEmpty()) {
   Node poppedNode = stack.pop();
   System.out.println(poppedNode);
   if (poppedNode.getRight() != null) {
    stack.add(poppedNode.getRight());
   }
   
   if (poppedNode.getLeft() != null) {
    stack.add(poppedNode.getLeft());
   }
  }
}


Inorder traversal
The recursive solution is pretty simple. Given a node, keep navigating to the left-most node until a leaf node is reached. Once reached, process the leaf node, its parent and then the right sub-tree (again go through the same above process).

public void inOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   inOrderTraversalRecursive(node.getLeft());
  }
  System.out.println(node);
  if (node.getRight() != null) {
   inOrderTraversalRecursive(node.getRight());
  }
 }

As expected the iterative solution uses a single stack. The in-order traversal algorithm processes the left sub-tree first from deep down node => which in turn means, navigate to the left-most leaf node. So, as a first step, navigate deep down into the left sub-tree. We keep pushing all the left-nodes to the stack when we navigate, so that when we pop out of the stack for the first time, it’s going to be the left-most leaf node. For every popped node, we check whether there is a right node, if there is, then we add that node and then followed by all left-nodes (if there are) for the right node (that we are working on) to the stack. Once that is done, we pop out a node from the stack and then repeat the same above process until the stack goes empty.

public void inOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }

  Stack<Node> stack = new Stack<Node>();
  // Navigate to the left most node of the left sub-tree. During that process, push all the navigating nodes to the stack.
  while (node != null) {
   stack.push(node);
   node = node.getLeft();
  }
  
  while (!stack.isEmpty()) {
   Node currNode = stack.pop();
   System.out.println(currNode);
   
   /* If the current node has a right child, push it to stack and navigate to the left node of that right child if it exists. 
   Remember we need to process the right sub-tree of any parent node. So, add all left nodes of the right child to stack and 
   keep navigating to left till the leaf node */ 
   if (currNode.getRight() != null) {
    Node rightnode = currNode.getRight();
    stack.push(rightnode);
    if (rightnode.getLeft() != null) {
     Node rightsLeftnode = rightnode.getLeft();
     while (rightsLeftnode != null) {
      stack.push(rightsLeftnode);
      rightsLeftnode = rightsLeftnode.getLeft();
     }
    }
   }
  }
 }


Postorder traversal
As always the recursive solution is simple. Given a node, the left descendants are processed first followed by the right descendants and then the node in consideration is processed. It looks pretty simple to do using a recursive approach.

public void postOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   postOrderTraversalRecursive(node.getLeft());
  }
  
  if (node.getRight() != null) {
   postOrderTraversalRecursive(node.getRight());
  }
  System.out.println(node);
 }

The iterative solution for postorder traversal is the most difficult of all. The below iterative solution uses a single stack. This algorithm may not look same as other solutions provided in internet. This solution worked well for the usecases that I tested and hopefully it works for everyone. The tough part of this solution is: Determining whether we are currently navigating down the tree or up the tree. If we don’t determine that, we might end up looping back and forth in an endless loop. How to identify whether we are going up or down? If we remember the previous node that was processed or added to the stack then based on that, we can tell the relationship of the current node to the previous node. It can be a child node or the parent node!! This determination would help us making a decision whether to move up or down.

On a broad view, there are 2 cases that need to be covered in this algorithm
1) If the current node is the parent of the previously processed node (the previously processed node could either be a left or right child) then it means we are going up the tree. That in turn means we have already processed the child sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
2) The other situations could be:
a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree.
b) The current node is the root node.
c) The current node can be the right companion of the previously processed node.

For all the above usecases (a), (b) and (c), we call the special private method “navigateAndProcessNodesInPostOrder” method. navigateAndProcessNodesInPostOrder method takes care of pushing the current node, left child and right child (in that order) to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold the previous processed node, the current node and the stack.

/**
  * An iterative solution for postorder traversal of a binary tree.
  * 
  * On a broad view, there are 2 cases that need to be covered in this algorithm
  * 1) If the current node is the parent of the previously processed node (the previously processed node could either be a 
  *   left or right child) then it means we are going up the tree. That in turn means we have already processed the child 
  *  sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
  * 2) The other situations could be: 
  *  a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree. 
  *  b) The current node is the root node. 
  *  c) The current node can be the right companion of the previously processed node. 
  *  For all the above usecases, we call the special private method “navigateAndProcessNodesInPostOrder” method. 
  *  navigateAndProcessNodesInPostOrder  method takes care of pushing the current node, left child and right child (in that order) 
  *  to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given 
  *  to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes 
  *  it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold 
  *  the previous processed node, the current node and the stack.
  * @param node Node Object
  * 
  */
 public void postOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }
  
  Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  Node prevNode = null;
  Node currNode = null;
  
  while (!stack.isEmpty()) {
   currNode = stack.pop();
   
   if (currNode.getLeft() == prevNode || currNode.getRight() == prevNode) {
    // If the current node is the parent of previously processed node. Navigating up the tree. So its enough just to process the node
    System.out.println(currNode);
    prevNode = currNode;
   } else {
    // If previously processed node was the parent of current node. i.e currently processing either the left or right child (navigating down).
    // If the node is the root node.
    // If the current node is the leaf node of a sub-tree. In this case previously processed node and current node are same.
    // If the current node being processed is the right companion of the previously processed node
    
    NodeWrapper nodeWrapper = new NodeWrapper(prevNode, currNode, stack);
    nodeWrapper = navigateAndProcessNodesInPostOrder(nodeWrapper);
    prevNode = nodeWrapper.getPrevNode();
    currNode = nodeWrapper.getCurrNode();
    stack = nodeWrapper.getStack();
   }
  }
 }
 
 /**
  * A helper method for post-order traversal - if given a node, it traverses and processes the sub-tree
  * NodeWrapper object is used to exchange prev, curr nodes and stack between the calling and called method
  * @param nodeWrapper
  * @return
  */
 private NodeWrapper navigateAndProcessNodesInPostOrder(NodeWrapper nodeWrapper) {
  Node currNode = nodeWrapper.getCurrNode();
  Node prevNode = nodeWrapper.getPrevNode();
  Stack<Node> stack = nodeWrapper.getStack();
  
  Node leftNode = currNode.getLeft();
  Node rightNode = currNode.getRight();
  if (leftNode != null  || rightNode != null) {
   // current node (if its a parent) is the last to be processed and so it has to be pushed to stack first
   stack.push(currNode);
   if (rightNode != null) {
    // If there is a right node, push it to stack
    stack.push(rightNode);
   }
   // If there is a left node, push it to stack
   if (leftNode != null) {
    stack.push(leftNode);
   }
   prevNode = currNode;
   
   // Left takes precedence. If there is a left node, go left else go right 
   if (leftNode != null) {
    currNode = currNode.getLeft();
   } else if (rightNode != null) {
    currNode = currNode.getRight();
   }
  } else { // its a leaf node, so process it
   System.out.println(currNode);
   prevNode = currNode;
  }
  nodeWrapper.setPrevNode(prevNode);
  nodeWrapper.setCurrNode(currNode);
  return nodeWrapper;
 }
 
  /**
  * An inner class NodeWrapper to encompass prevNode, currNode and stack for post-order traversal
  *
  */
 class NodeWrapper {
  private Node prevNode;
  private Node currNode;
  private Stack<Node> stack;
  
  NodeWrapper(Node prevNode, Node currNode, Stack<Node> stack) {
   this.prevNode = prevNode;
   this.currNode = currNode;
   this.stack = stack;
  }

  private Node getPrevNode() {
   return prevNode;
  }

  private Node getCurrNode() {
   return currNode;
  }

  private Stack<Node> getStack() {
   return stack;
  }

  private void setPrevNode(Node prevNode) {
   this.prevNode = prevNode;
  }

  private void setCurrNode(Node currNode) {
   this.currNode = currNode;
  }

  private void setStack(Stack<Node> stack) {
   this.stack = stack;
  }
  
 }


The entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms. I have added as many comments as possible in the code. Hope it will help everyone!!

Labels: , ,

Monday, December 16, 2013

Linked List

Linked lists are the most important type of data structure. It contains a series of special elements. These special elements are called special because they hold the data and a pointer to the next element. This pointer is usually called as next pointer. The root element is the starting point of the linked list and the tail element is the last element in the linked list. After the tail element there are no more elements and so the last element’s next pointer has a null reference.

There are 3 types of linked lists
1) Single Linked List – There is one next reference per element
2) Double Linked List – There are two references per element called prev and next. The prev reference points to the previous element and the next reference points to the next element as always
3) Circular Linked List – This is a special type of linked list and they can be of Single or double linked list. The important property that differentiates them is that they do not have the end elements. Yes, there are no head or tail elements. It means that if you start from any element and traverse, you will end up in going circles and never end.

This project illustrates the various operations that can be done on a Single Linked List. Additionally it also shows a special stack implementation using Single Linked List.

Traverse and Print All Elements
Traverses the entire linked list and prints all elements.
 /**
  * Prints all elements in the linked list to out stream
  * @param void
  * @return void
  */
 public void print() {
  Element currElement = head;
  while (currElement != null) {
   System.out.println(currElement);
   currElement = currElement.getNext();
  }
 }


Add an element to the end
This adds the given data as an element to the end of the linked list. Now the new element becomes the tail element.
 /**
  * Adds the provided Integer object data to the end of linked list
  * @param data Integer
  * @return boolean
  */
 public boolean add(Integer data) {
  Element newElement = new Element(data);
  if (head == null) {
   head = newElement;
   return true;
  } else {
   Element prevElement = head;
   Element currElement = head.getNext();
   while (currElement != null) {
    prevElement = currElement;
    currElement = currElement.getNext();
   }
   if (prevElement != null) {
    prevElement.setNext(newElement);
    return true;
   }
  }
  return false;
 }


Add an element at the specified position
Given an integer data, this method creates an element out of it and adds at the specified position of the list.
 /**
  * Inserts the provided Integer object data at the requested position of linked list.
  * If insert was successful it returns true else returns false
  * 
  * 
  * Implementation Details:
  * Though the iteration variable tracks the position of current Element pointer, if a position
  * is found where the new element needs to be inserted, it is implicit that the position is going to be
  * in between the prevElement and curreElement. Idea is to visualize the position (input) to be in between 
  * prevElement and currElement
  * 
  * Say if the position is after the last element then it means you have to insert after the prevElement(pointing last element)
  * but before the curreElement (which is pointing a virtual non-existent element - beyond last element). So its imperative that 
  * the while loop runs until the prevElement is pointing the last element
  * 
  * @param data Integer
  * @param position Long
  * @return boolean
  * 
  */
 public boolean add(Integer data, Long position) {
  
  if (position == null || position.intValue() < 1) {
   return false;
  }
  
  if (head != null) {
   Element newElement = new Element(data);
   if (position.intValue() == 1) {
    newElement.setNext(head);
    head = newElement;
   } else {
    Element prevElement = head;
    Element currElement = head.getNext();
    int iteration = 2;
    while (prevElement != null) {
     if (iteration == position.intValue()) {
      newElement.setNext(currElement);
      prevElement.setNext(newElement);
      return true;
     } else {
      prevElement = currElement;
      currElement = currElement.getNext();
      iteration++;
     }
    }
   }
  }
  
  return false;
 }



Delete an element from the given position
Given a position in linked list, this deletes the element at that position. If there is no such position in the list, then it does not delete anything from the linked list.
 /**
  * This method deletes all elements in the linked list that have the provided Integer data. 
  * If one or many elements are deleted, this method returns true else it returns false
  * @param data Integer
  * @return boolean
  */
 public boolean delete(Integer data) {
  Element givenElement = new Element(data);
  boolean deleted = false;
  
  // Special case if the head element needs to be deleted
  if (head.equals(givenElement)) {
   Element temp = head;
   head = head.getNext();
   temp.setNext(null);
   deleted = true; 
  }
  
  if (head != null) {
   Element prevElement = head;
   Element currElement = head.getNext();
   while (currElement != null) {
    if (currElement.equals(givenElement)) {
     prevElement.setNext(currElement.getNext());
     currElement = currElement.getNext();
     deleted = true;
    }
    prevElement = currElement;
    currElement = currElement.getNext();
   }
  }
  return deleted;
 }


Delete all elements with a given data
Deletes all elements that have the given data. Takes care of chaining the element appropriately after the deletion is complete.
 /**
  * This method deletes the element at requested position of the linked list. 
  * If deletion happens, this method returns true else it returns false
  * @param position Long
  * @return boolean
  */
 public boolean delete(Long position) {
  if (position == null || position.intValue() < 1) {
   return false;
  }

  if (head != null) {
   if (position.intValue() == 1) {
    Element temp = head;
    head = head.getNext();
    temp.setNext(null);
    return true;
   } else {
    int iteration = 2;
    Element prevElement = head;
    Element currElement = head.getNext();
    while (currElement != null) {
     if (iteration == position.intValue()) {
      prevElement.setNext(currElement.getNext());
      currElement.setNext(null);
      return true;
     }
     prevElement = currElement;
     currElement = currElement.getNext();
     iteration++;
    }
   }
  }

  return false;
 }


Clear all elements (delete all)
Deletes all elements that have the given data. Takes care of chaining the element appropriately after the deletion is complete.
 /**
  * Deletes all elements in the linked list. 
  * If all elements are deleted, this method returns true else it returns false
  * @param void
  * @return boolean
  */
 public boolean clear() {
  if (head == null) {
   return false;
  }
  
  while (head != null) {
   Element element = head;
   head = head.getNext();
   element.setNext(null);
  }
  return true;
 }


Get Element At
Gets the data from the element at the specified position. If there are no elements at the given position, then this method returns null.
 /**
  * Returns the element at requested position of the linked list. 
  * The position is counted from the head element.
  * @param position Long
  * @return Element
  */
 public Element getElementAt(Long position) {
  
  if (position == null || head == null || position.intValue() < 1) {
   return null;
  }
  
  int iteration = 1;
  Element currElement = head;
  while (currElement != null) {
   if (position.intValue() == iteration) {
    return currElement;
   }
   currElement = currElement.getNext();
   iteration++;
  }

  return null;
 }


Get Nth Element From Last
Get Nth element from the tail element of the linked list. The first thought that strike's everyone is – Navigate to the tail element of the linked list and return the Nth previous element from there. But the point that we all tend to forget is - we can traverse only forward in a single linked list. We cannot traverse backwards, and so it makes the solution pretty tricky. The idea is to have two references in the linked list, say A and B. As a first step, have them separated by N elements. This is done by forwarding the B reference by N elements and thereafter keep traversing both references until B reaches tail element. When B is referring the tail element, this in turn means that A is N elements before the tail element.
 /**
  * Returns the element at requested position of the linked list. 
  * The position is counted from the tail or last element of the linked list.
  * @param position Long
  * @return Element
  */
 public Element getNthFromLastElement(Long position) {
  
  if (position == null || head == null || position.intValue() < 1) {
   return null;
  }
  
  Element currElement = head;
  Element nthBehindElement = head;
  int iteration = 1;
  
  while (currElement != null && iteration <= position.intValue()) {
   if (iteration++ == position.intValue()) {
    break; 
   }
   currElement = currElement.getNext();
  }
  
  if (currElement == null) {
   System.out.println("** Error: Current Element is past tail element");
   return null;
  }
  
  while (currElement.getNext() != null) {
   currElement = currElement.getNext();
   nthBehindElement = nthBehindElement.getNext();
  }
  
  return nthBehindElement;
 }


Stack Implementation
This implementation of Stack is done using a linked list. Stack is a simple LIFO data structure. There are two major actions that you can perform on a stack. Push and Pop. Additionally we have a clear operation that deletes all elements in the stack. And lastly we have print operation that prints all elements in the stack.
 /**
  * Returns true if stack is empty else returns false
  * @return boolean
  */
 public boolean isEmpty() {
  if (this.head == null) {
   return true;
  }
  return false;
 }
 
 /**
  * Returns true if the method was able to push data to the stack. Else returns false.
  * @param data Integer
  * @return boolean
  */
 public boolean push(Integer data) {
  if (data == null) {
   return false;
  }
  
  Element newElement = new Element(data);
  if (head == null) {
   head = newElement;
   return true;
  }
  
  if (head != null) {
   Element temp = head;
   head = newElement;
   head.setNext(temp);
   return true;
  }
  
  return false;
 }
 
 
 /**
  * Pops and returns the last element that was pushed to the stack
  * @return stackElement
  */
 public Element pop() {
  Element element = null;
  if (head == null) {
   System.out.println("Stack is empty!! Cannot pop anything out of it!!");
   return element;
  }
  
  Element firstElement = head;
  Element secondElement = head.getNext();
  head = secondElement;
  firstElement.setNext(null);
  return firstElement;
 }
 
 
 /**
  * Returns true if stack was cleared or if it was empty already
  * @return boolean
  */
 public boolean clear() {
  while (head != null) {
   Element element = head;
   head = head.getNext();
   element.setNext(null);
  }
  return true;
 }
 
 
 /**
  * Iterates over the stack and prints all its elements
  */
 public void printAll() {
  if (head == null) {
   System.out.println("Stack is empty currently!!");
   return;
  }
  
  Element currElement = head;
  while (currElement != null) {
   System.out.println(currElement);
   currElement = currElement.getNext(); 
  }
 }


The entire code base for this project can be accessed from my Github repository – Linked List algorithms. I have added as many comments as possible in the code. Hope it helps!!

Labels: , ,

Friday, December 13, 2013

All Posts

Labels: