Datastructures

Following figure shows the levels in a tree level order traversal of the tree is 1, 2, 3, 4, 5     We are given the root node and we are supposed to print its level order traversal. If we closely examine the steps first we have to do is to print the root node (i.e 1 in the example) then we have to keep track of it's child nodes. Now we have to print 2 and 3 and keep track of their child nodes. It is clear that we cannot simply use a tempnode to keep track of the values in each iteration. And we also need to keep track of the order that is 2 followed by 3 followed by 4 and so on.    So we are going to use queue data structure here. After printing a node we will enqueue its child elements to the queue. We ll repeat the same procedure until the queue becomes empty. Lets see it more clearly with code and illustration. Code:  void levelOrder(Node root) {     Queue<Node> queue=new LinkedList<>();     queue.add(...

Preorder traversal: In preorder traversal root is visited first. Steps: 1. Visit the root 2. Traverse the left subtree 3. Traverse the right subtree Code: void preOrder(Node root) { if(root==null) return; System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } Illustration: Preorder traversal of given tree is 1, 2, 3, 4, 5   Visit the root   Traverse the left subtree    Traverse the right subtree   Visit the root    Traverse the left subtree    Traverse the right subtree

Postorder traversal: In postorder traversal root is visited at the last. Steps: 1. Traverse the left subtree 2. Traverse the right subtree 3. Visit the root Code: void postOrder(Node root) { if(root==null) return; postOrder(root.left); postOrder(root.right); System.out.print(root.data+" "); } Illustration: Postorder traversal of given tree is 2, 4, 5, 3, 1 Traverse the left subtree   Traverse the right subtree   Traverse the left subtree   Traverse the right subtree   Visit the root   Visit the root ( since we finished traversing left and right subtrees of 7 )

        A binary tree can be traversed in two ways. i) Depth First Traversal: Inorder, preorder, postorder ii) Breadth First Traversal: Level Order Traversal Inorder traversal:        In inorder traversal root is visited in between left and right subtree traversals. Steps: 1.  Traverse the left subtree 2.  Visit the root 3. Traverse the right subtree Note: If binary search tree is traversed in inorder, the numbers will be sorted in ascending order. Code: void inOrder(Node root) { if(root==null) return; inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } Illustration: Inorder traversal of given tree is 3, 5, 4, 7, 8  Consider the left subtree of 7 (since 7 is the root ,we always start our traversal from root) Here we start form 5, the left subtree of 5 is 3. For 3 the left subtree is empty , So we visit the root. The right subtree of tree is also empty. At ...

   A tree in which every node can have a maximum of two children is called a binary tree.       A binary search tree is a binary tree in which every node has lower values in the left sub tree and higher values in the right sub tree. Node of binary tree: class Node{      int data;      Node left, right;      Node(int data){         this.data = data;         right = left = null;      } } BST - Insertion:  static Node Insert(Node root,int data) {      if( root == null ){            root = new Node(data);            return root;      }      if( data < root.data)             root.left = Insert(root.left,data);      else             root.right = Insert(root.rig...

Push operation: 1. create a new node with the given element. 2. Make the next of the new node to point to the top element. 3. Make top element to point to the new node. Pop operation: 1. Store the data of top element. 2. Make top to point to top->next. (you need not free the memory here since java makes garbage collection for unused references) Code: import java.util.*; import java.lang.*; import java.io.*; class Node {      int data;      Node next;            Node(int data){          this.data = data;          next = null;      }      } class Stack {     Node top = null;     public int pop(){         if (top == null){             System.out.println("stack is empty");             return 0;      ...

    Introduction:    Stack is a linear data structure which follows LIFO( Last In First Out ) order.   To represent stack consider books are placed in table for the teacher to correct. The note which is submitted last will be corrected first. The person who submits last is quite unlucky isn't it :P Operations: push: Inserts element at the top of the stack pop: Removes element from the top of the stack Stack implementation using array: Code: import java.util.*; import java.lang.*; import java.io.*; class Stack {     int SIZE = 10;     int arr[] = new int[SIZE];     int top = -1;          public int pop(){         if (top == -1){             System.out.println("stack is empty");             return 0;         }         int topelement ...

Input list : 1->2->3->4->|| Output list : 4->3->2->1->|| Code: Node reverse(Node head) {         Node prev = null;         Node current = head;         while (current != null) {             Node temp = current.next;             current.next = prev;             prev = current;             current = temp;         }         head = prev;         return head;     } Calling function: head = list.reverse(head); Illustration:  (note : images in order left column first followed by right column) i) Initialization and execution of first while loop ii) Execution of second while loop iii) Execution of final while loop and termination

Iterative solution: The key point here is initialize count = 0 and currentNode = head.  Increment counter when currentNode != null. currentNode = currentNode->next Code: int count (Node head){             currentNode = head;             int count = 0;             while(currentNode != null){                    count++;                    currentNode = currentNode->next;              }              return count; } Recursive solution: Recursively call 1+getCount(Node  head) If head is null return 0. Its the base condition. Code: int getCount(Node head){              if( head == null )               ...

Swap nodes in a linked list without swapping the data Sample input: swap 2 and 9 in 1->5->2->3->9->4 Sample output: 1->5->9->3->2->4 Steps: 1) find X,Y in the list and also their previous nodes. 2) prevX.next = Y and prevY.next = X 3) temp = X.next , X.next = Y.next, Y.next = temp Code: void swapNodes(int x, int y) {         Node prevX = null, X = head;         while (X != null && X.data != x)         {             prevX = X;             X = X.next;         }         Node prevY = null, Y = head;         while (Y != null && Y.data != y)         {             prevY = Y;             Y = Y.next;         }         if (prevX...