Binary Tree Implementation : Basic and Advanced Operation

Binary Trees

Introduction

We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.

More tree terminology:

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.
• A full binary tree.is a binary tree in which each node has exactly zero or two children.
• A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

A complete binary tree is very special tree, it provides the best possible ratio between the number of nodes and the height. The height h of a complete binary tree with N nodes is at most O(log N). We can easily prove this by counting nodes on each level, starting with the root, assuming that each level has the maximum number of nodes:

n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1

Solving this with respect to h, we obtain

h = O(log n)

where the big-O notation hides some superfluous details.

Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move subtrees around with minumum effort

Traversals

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds

• depth-first traversal
• breadth-first traversal

There are three different types of depth-first traversals, :

• PreOrder traversal - visit the parent first and then left and right children;
• InOrder traversal - visit the left child, then the parent and the right child;
• PostOrder traversal - visit left child, then the right child and then the parent;

There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.

As an example consider the following tree and its four traversals: PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3 InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11 PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8 LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2

In the next picture we demonstarte the order of node visitation. Number 1 denote the first node in a particular traversal and 7 denote the last node.
These common traversals can be represented as a single algorithm by assuming that we visit each node three times. An Euler tour is a walk around the binary tree where each edge is treated as a wall, which you cannot cross. In this walk each node will be visited either on the left, or under the below, or on the right. The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit nodes from the below, we get an inorder traversal. And when we visit nodes on the right, we get a postorder traversal.

1:  package com.examples.ajay;  
2:  import java.util.ArrayDeque;  
3:  import java.util.ArrayList;  
4:  import java.util.List;  
5:  import java.util.Queue;  
6:  import java.util.Stack;  
7:  import org.w3c.dom.ls.LSInput;  
8:  class Node{  
9:       int data;  
10:       Node left;  
11:       Node right;  
12:  }  
13:  class Item{  
14:       int data;  
15:       int level;  
16:  }  
17:  class Height{  
18:       int data;  
19:  }  
20:  public class BinaryTreeImplementation {  
21:       private static int count = 0;  
22:       private static int preOrderIndex = 0;  
23:       public static int max(int i, int j) {  
24:            if(i < j) return j;  
25:            else return i;  
26:       }  
27:       public static void preorder(Node node){  
28:            if(node == null) return;  
29:            System.out.print(node.data + " ");  
30:            preorder(node.left);  
31:            preorder(node.right);  
32:       }  
33:       public static void postorder(Node node){  
34:            if(node == null) return;  
35:            postorder(node.left);  
36:            postorder(node.right);  
37:            System.out.print(node.data + " ");  
38:       }  
39:       public static void inorder(Node node){  
40:            if(node == null) return;  
41:            inorder(node.left);  
42:            System.out.print(node.data + " ");  
43:            inorder(node.right);  
44:       }  
45:       public static void levelOrder(Node node){  
46:            Queue<Node> queue = new ArrayDeque<Node>();  
47:            queue.add(node);  
48:            while(!queue.isEmpty()){  
49:                 Node temp = queue.remove();  
50:                 System.out.print(temp.data + " ");  
51:                 if(temp.left != null) queue.add(temp.left);  
52:                 if(temp.right != null) queue.add(temp.right);  
53:            }  
54:       }  
55:       public static void preorderIteration(Node node){  
56:            Stack<Node> stack = new Stack<Node>();  
57:            stack.push(node);  
58:            while(!stack.isEmpty()){  
59:                 Node temp = stack.pop();  
60:                 System.out.print(temp.data + " ");  
61:                 if(temp.right != null) stack.push(temp.right);  
62:                 if(temp.left != null) stack.push(temp.left);  
63:            }  
64:       }  
65:       public static void postorderIteration(Node node){  
66:            Stack<Node> stack = new Stack<Node>();  
67:            if(node == null) return;  
68:            do{  
69:                 while(node != null){  
70:                   if(node.right != null)     stack.push(node.right);  
71:                      stack.push(node);  
72:                      node = node.left;  
73:                 }  
74:                 node = stack.pop();  
75:                 if((node.right != null) && (!stack.isEmpty()) && (node.right == stack.peek())){  
76:                      stack.pop();  
77:                      stack.push(node);  
78:                      node = node.right;  
79:                 }else{  
80:                      System.out.print(node.data + " ");  
81:                      node = null;  
82:                 }  
83:            }while(!stack.isEmpty());  
84:       }  
85:       public static void inorderIteration(Node node){  
86:            Stack<Node> stack = new Stack<Node>();  
87:            if(node == null) return;  
88:            do{  
89:                 while(node != null){  
90:                      stack.push(node);  
91:                      node = node.left;  
92:                 }  
93:                 if(stack.empty()) break;  
94:                 node = stack.pop();  
95:                 System.out.print(node.data + " ");  
96:                 node = node.right;  
97:            }while(true);  
98:       }  
99:       public static int maximum(Node root){  
100:            int max = Integer.MIN_VALUE;  
101:            int left, right;  
102:            if(root == null) return max;  
103:            left = maximum(root.left);  
104:            right = maximum(root.right);  
105:            if(left > right) max = left;  
106:            else max = right;  
107:            if(max < root.data) max = root.data;  
108:            return max;  
109:       }  
110:       public static boolean searchElement(Node root, int data){  
111:            boolean isLeft = false;  
112:            boolean isRight = false;  
113:            if(root == null) return false;  
114:            if(root.data == data) return true;  
115:            isLeft = searchElement(root.left, data);  
116:            isRight = searchElement(root.right, data);  
117:            if(isLeft == false && isRight == false) return false;  
118:            else return true;  
119:       }  
120:       public static int sizeOfTree(Node root){  
121:            if(root == null) return 0;  
122:            int leftSize = sizeOfTree(root.left);  
123:            int rightSize = sizeOfTree(root.right);  
124:            return leftSize + rightSize + 1;  
125:       }  
126:       public static Node createFullBST(int height){  
127:            if(height == 0) return null;  
128:            Node temp = new Node();  
129:            temp.left = createFullBST(height-1);  
130:            temp.data = count++;  
131:            temp.right = createFullBST(height-1);  
132:            return temp;  
133:       }  
134:       public static int heightTree(Node root){  
135:            if(root == null) return 0;  
136:            int leftHeight = heightTree(root.left) + 1;  
137:            int rightHeight = heightTree(root.right) + 1;  
138:            if(leftHeight > rightHeight ) return leftHeight;  
139:            else return rightHeight;  
140:       }  
141:       public static Item deepestNode(Node root, int level){  
142:            if(root == null) return null;  
143:            Item left = deepestNode(root.left, level+1);  
144:            Item right =deepestNode(root.right, level+1);  
145:            if(left == null && right == null){  
146:                 Item item = new Item();  
147:                 item.data = root.data;  
148:                 item.level = level;  
149:                 return item;  
150:            }else{  
151:                 if(left != null && right != null){  
152:                      if(left.level > right.level){  
153:                           return left;  
154:                      }else{  
155:                           return right;  
156:                      }  
157:                 }  
158:                 else if(left == null) return right;  
159:                 else return left;  
160:            }  
161:       }  
162:       public static boolean isIdentical(Node root1, Node root2){  
163:            if(root1 == null && root2 == null) return true;  
164:            if(root1 == null || root2 == null) return false;  
165:            if(root1.data == root2.data){  
166:                 boolean isLeft = isIdentical(root1.left, root2.left);  
167:                 boolean isRight = isIdentical(root1.right, root2.right);  
168:                 if(isLeft == true && isRight == true) return true;  
169:                 else return false;  
170:            }else return false;  
171:       }  
172:       public static Height diameterTree(Node root, Height height){  
173:            Height leftHeight = new Height();  
174:            Height rightHeight = new Height();  
175:            if(root == null){  
176:                 height.data = 0;  
177:                 return height;  
178:            }  
179:            Height ldiameter = diameterTree(root.left, leftHeight);  
180:            Height rdiameter = diameterTree(root.right, rightHeight);  
181:            height.data = max(leftHeight.data, rightHeight.data) + 1;  
182:            Height newHeight = new Height();  
183:            newHeight.data = max(leftHeight.data + rightHeight.data + 1, max(ldiameter.data, rdiameter.data));  
184:            return newHeight;  
185:       }  
186:       public static void allPathToLeaf(Node root, int[] list, int pathLength){  
187:            if(root == null) return;  
188:            list[pathLength] = root.data;  
189:            pathLength++;  
190:            if(root.left == null && root.right == null){  
191:                 for(int i = 0; i < pathLength; i++){  
192:                      System.out.print(list[i] + " -> ");  
193:                 }  
194:                 System.out.println();  
195:            }else{  
196:                 allPathToLeaf(root.left, list, pathLength);  
197:                 allPathToLeaf(root.right, list, pathLength);  
198:            }  
199:       }  
200:       public static boolean isPathWithSum(Node root, int sum){  
201:            if(sum == 0) return true;  
202:            if(sum != 0 && root == null) return false;  
203:            if(sum < 0) return false;  
204:            sum -= root.data;  
205:            boolean leftpart = isPathWithSum(root.left, sum);  
206:            boolean rightpart = isPathWithSum(root.right, sum);  
207:            if(leftpart || rightpart) return true;  
208:            else return false;  
209:       }  
210:       public static int sumAllElements(Node root){  
211:            if(root == null) return 0;  
212:            int leftSum = sumAllElements(root.left);  
213:            int rightSum = sumAllElements(root.right);  
214:            return leftSum + rightSum + root.data;  
215:       }  
216:       public static void getMirror(Node root){  
217:            if(root == null) return;  
218:            Node temp = root.left;  
219:            root.left = root.right;  
220:            root.right = temp;  
221:            getMirror(root.left);  
222:            getMirror(root.right);  
223:       }  
224:       public static Node constuctPreorderInorderTree(int[] preorder, int[] inorder, int inStart, int inEnd){  
225:            if(inStart > inEnd) return null;  
226:            Node node = new Node();  
227:            node.data = preorder[preOrderIndex++];  
228:            int index = search(inorder, node.data, inStart, inEnd);  
229:            if(index != -1){  
230:                 node.left = constuctPreorderInorderTree(preorder, inorder, inStart, index - 1);  
231:                 node.right = constuctPreorderInorderTree(preorder, inorder, index + 1, inEnd);  
232:            }  
233:            return node;  
234:       }  
235:       private static int search(int[] inorder, int key, int inStart, int inEnd) {  
236:            for(int i = inStart; i <= inEnd; i++) if(inorder[i] == key) return i;  
237:            return -1;  
238:       }  
239:       private static boolean printAncesstor(Node node, int key){  
240:            if(node == null) return false;  
241:            if(node.data == key){  
242:                 System.out.print(node.data+ " ");  
243:                 return true;  
244:            }  
245:            boolean isLeft = printAncesstor(node.left, key);  
246:            boolean isRight = printAncesstor(node.right, key);  
247:            if(isLeft || isRight){  
248:                 System.out.print(node.data + " ");  
249:                 return true;  
250:            }else return false;  
251:       }  
252:       public static void main(String[] args) {  
253:            Node root = createFullBST(4);  
254:            System.out.println("Preorder with recursion : ");   
255:            preorder(root);  
256:            System.out.println("\nPreorder without recursion : ");   
257:            preorderIteration(root);  
258:            System.out.println("\nPostorder with recursion : ");   
259:            postorder(root);  
260:            System.out.println("\nPostorder without recursion : ");   
261:            postorderIteration(root);  
262:            System.out.println("\nInorder with recursion : ");   
263:            inorder(root);  
264:            System.out.println("\nInorder without recursion : ");   
265:            inorderIteration(root);  
266:            System.out.println("\nLevel with recursion : ");   
267:            levelOrder(root);  
268:            System.out.println("\n\nMaximum in Tree is : "+ maximum(root));  
269:            if(searchElement(root, 5)){  
270:                 System.out.println("\nYes !! Present");  
271:            }else System.out.println("\nNo !! Not Present");  
272:            System.out.println("\nSize of Tree : "+sizeOfTree(root));  
273:            System.out.println("\nHeight of Tree : "+heightTree(root));  
274:            Node node1 = new Node();  
275:            node1.data = 1;  
276:            node1.left = new Node();  
277:            node1.left.data = 2;  
278:            node1.right = new Node();  
279:            node1.right.data = 3;  
280:            node1.left.left = new Node();  
281:            node1.left.left.data = 4;  
282:            node1.right.right = new Node();  
283:            node1.right.right.data =5;  
284:            node1.left.left.left = new Node();  
285:            node1.left.left.left.data = 6;  
286:            Node node2 = new Node();  
287:            node2.data = 1;  
288:            node2.left = new Node();  
289:            node2.left.data = 2;  
290:            node2.right = new Node();  
291:            node2.right.data = 3;  
292:            node2.left.left = new Node();  
293:            node2.left.left.data = 4;  
294:            node2.right.right = new Node();  
295:            node2.right.right.data =5;  
296:            node2.left.left.left = new Node();  
297:            node2.left.left.left.data = 9;  
298:            node2.left.right = new Node();  
299:            node2.left.right.data = 6;  
300:            node2.left.right.right = new Node();  
301:            node2.left.right.right.data = 7;  
302:            node2.left.right.right.right = new Node();  
303:            node2.left.right.right.right.data = 8;  
304:            Item deepest = deepestNode(node1, 0);  
305:            System.out.println("\nDeepest node of Tree : "+deepest.data);  
306:            System.out.println("\nIs tow Trees Identcal : "+ isIdentical(node1, node2));  
307:            Height height = new Height();  
308:            height.data = 0;  
309:            System.out.println("\nDiameter of tree : "+ diameterTree(node2, height).data);  
310:            int[] list = new int[1000];  
311:            allPathToLeaf(node2, list, 0);  
312:            System.out.println("\nDoes it have path : "+ isPathWithSum(node2, 10));  
313:            System.out.println("\nSum all elements of tree : "+sumAllElements(root));  
314:            System.out.println("\nBefore Mirror :");  
315:            preorder(node2);  
316:            getMirror(node2);  
317:            System.out.println("\nAfter Mirror :");  
318:            preorder(node2);  
319:            System.out.println("\n=================================================================");  
320:            int[] inorder = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };  
321:            int[] preorder = {7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14};  
322:            Node constructedTree = constuctPreorderInorderTree(preorder, inorder, 0, inorder.length - 1);  
323:            postorder(constructedTree);  
324:            System.out.println("\n=================================================================");  
325:            System.out.println("\nAncesstors : "+ printAncesstor(node2, 8));  
326:       }  
327:  }  

Heap Implementation in JAVA

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).

In a heap, the highest (or lowest) priority element is always stored at the root, hence the name heap. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.

1:  package com.examples.ajay;  
2:  class Heap{  
3:       int[] array;  
4:       int count;  
5:       int capacity;  
6:       int heap_type;  
7:  }  
8:  public class HeapImplementation {  
9:       public static Heap createHeap(int capacity, int heap_type){  
10:            Heap heap = new Heap();  
11:            heap.array = new int[capacity];  
12:            if(heap.array == null) return null;  
13:            heap.heap_type = heap_type;  
14:            heap.count = 0;  
15:            heap.capacity = capacity;  
16:            return heap;  
17:       }  
18:       public static int getParent(Heap heap, int i){  
19:            if(i >= heap.count || i <= 0) return -1; //asking for parent of root or entry outside the amount of elements in heap  
20:            return (i-1)/2;  
21:       }  
22:       public static int leftChild(Heap heap, int i){  
23:            int left = 2*i + 1;  
24:            if(left >= heap.count) return -1;  
25:            else return left;  
26:       }  
27:       public static int rightChild(Heap heap, int i){  
28:            int right = 2*i + 2;  
29:            if(right >= heap.count) return -1;  
30:            else return right;  
31:       }  
32:       public static int getMaximum(Heap heap){  
33:            if(heap.count <= 0) return -1;  
34:            else return heap.array[0];  
35:       }  
36:       public static void heapify(Heap heap , int i){  
37:            int left, right, max;  
38:            left = leftChild(heap, i);  
39:            right = rightChild(heap, i);  
40:            //exchange parent with the maximum among both of left or right children  
41:            if(left != -1 && heap.array[left] > heap.array[i]) max = left;  
42:            else max = i;  
43:            if(right != -1 && heap.array[right] > heap.array[max]) max = right;  
44:            if(max != i){  
45:                 int temp = heap.array[max];  
46:                 heap.array[max] = heap.array[i];  
47:                 heap.array[i] = temp;  
48:                 heapify(heap, max);  
49:            }  
50:       }  
51:       public static int deleteMax(Heap heap){  
52:            int data;  
53:            if(heap.count <= 0) return -1;  
54:            data = heap.array[0];  
55:            heap.array[0] = heap.array[heap.count - 1];  
56:            heap.count--;  
57:            heapify(heap, 0);  
58:            return data;  
59:       }  
60:       public static void insert(Heap heap, int data){  
61:            if(heap.count == heap.capacity) resizeHeap(heap);  
62:            heap.count++;  
63:            int i = heap.count - 1;  
64:            //find location till data is greater than the parent of node which is inserted at count-1  
65:            while(i > 0 && data > heap.array[(i-1)/2]){  
66:                 heap.array[i] = heap.array[(i-1)/2];  
67:                 i = (i-1)/2;  
68:            }  
69:            heap.array[i] = data;  
70:       }  
71:       private static void resizeHeap(Heap heap) {  
72:            // TODO Auto-generated method stub  
73:            int i = 0;  
74:            int[] temp = heap.array;  
75:            heap.array = new int[heap.capacity * 2];  
76:            for (int element : temp) {  
77:                 heap.array[i++] = element;  
78:            }  
79:            heap.capacity *= 2;  
80:       }  
81:       public static void main(String[] args) {  
82:            // TODO Auto-generated method stub  
83:            int[] heapArray = {3, 1, 9, 8, 14, 12, 5, 7, 31, 10, 16};  
84:            Heap heap = createHeap(heapArray.length, 0);  
85:            /*for(int element : heapArray){  
86:                 insert(heap, element);  
87:            }*/  
88:            int i = 0;  
89:            for(int element : heapArray){  
90:                 heap.array[i++] = element;  
91:            }  
92:            heap.count = heapArray.length;  
93:            for(i = (heapArray.length - 1)/2; i >= 0 ; i--) heapify(heap, i);  
94:            System.out.println("Results: ");  
95:            for(i = 0; i < heap.count ; i++){  
96:                 System.out.print(heap.array[i] + " ");  
97:            }  
98:            System.out.println();  
99:            System.out.println("Deleing root ...");  
100:            deleteMax(heap);  
101:            System.out.println("Results: ");  
102:            for(i = 0; i < heap.count ; i++){  
103:                 System.out.print(heap.array[i] + " ");  
104:            }  
105:       }  
106:  }  

Output :

Results: 

31 16 12 9 14 3 5 1 7 8 10 

Deleting root ...

Results: 

16 14 12 9 10 3 5 1 7 8 

Sort elements by frequency

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

Examples:

Input:  arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}

 Input 5  2  2  8  5  6  8  8

  After sorting we get
  Element 2 2 5 5 6 8 8 8
  Index   1 2 0 4 5 3 6 7

  Now construct the 2D array as
  Index, Count
  1,      2
  0,      2
  5,      1
  3,      3

  Sort by count (consider indexes in case of tie)
  3, 3
  0, 2
  1, 2
  5, 1
  
  Print the elements using indexes in the above 2D array.

=================================================

JAVA IMPLEMENTATION

=================================================

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Set;

class Element{

int value;

int index;

int count;

public Element(int value, int index, int count){

this.value = value;

this.index = index;

this.count = count;

}

}

public class SortElementByFrequency {

public static void main(String[] args) {

int array[] = {2, 5, 2, 6, -1, 999999, 5, 8, 8, 8};

int index = 0;

Map<Integer, Element> map = new HashMap<Integer , Element>();

for (int value : array) {

Element element = new Element(value, index, 1);

index++;

if(map.get(element.value) != null){

Element newelement = map.get(element.value);

newelement.count += 1;

map.put(element.value, newelement);

}else{

map.put(element.value, element);

}

}

Set<Integer> keys = map.keySet();

List<Element> list = new ArrayList<Element>();

for (Integer key : keys) {

list.add(map.get(key));

}

Collections.sort(list, new Comparator<Element>() {

@Override

public int compare(Element e1, Element e2) {

// TODO Auto-generated method stub

if(e2.count-e1.count != 0){

return e2.count-e1.count;

}else{

return e1.index-e2.index;

}

}

});

for (Element element : list) {

int count = element.count;

while(count > 0){

System.out.print(element.value + "  ");

count--;

}

}

}

}

Maximum sum such that no two elements are adjacent

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

package com.examples.ajay;

public class MaxSumNoAdjacentElement {

  private static int max(int i, int j) {

// TODO Auto-generated method stub

if(i < j) return j;

else return i;

}

private static void findSum(int[] array) {

// TODO Auto-generated method stub

int inclusive = array[0]; 
  // Max sum including current element. (If current included, prev     have to be excluded)

int exclusive = 0;
  // Max sum excluding current element : max (prev-incl, prev-excl) 

for(int i = 1; i< array.length; i++){

int temp = inclusive;

inclusive = exclusive + array[i];

exclusive = max(exclusive, temp);

}

System.out.println("Result : "+ max(inclusive, exclusive));

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int array[] = {5, 5, 10, 40, 50, 35};

findSum(array);

}

}

Program for array rotation

Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Rotation of the above array by 2 will make array

METHOD 1 (Use temp array)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
1) Store d elements in a temp array
   temp[] = [1, 2]
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2]

Time complexity O(n)
Auxiliary Space: O(d)

METHOD 2 (Rotate one by one)

leftRotate(arr[], d, n)
start
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
endTime complexity: O(n*d)

Auxiliary Space: O(1)

METHOD 3 (A Juggling Algorithm)
This is an extension of method 2. Instead of moving one by one, divide the array in different sets
where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below diagram for this movement)



          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b) Then in second set.
          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c) Finally in third set.
          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Java Code for Juggler Algorithm :

package com.examples.ajay;


public class RotateArrrayJugglerWay {

 private static int findGCD(int n, int d){
  if(n % d == 0) return d;
  else return findGCD(d, n % d);
 }
 private static void leftRotate(int[] array, int dist, int length) {
  // TODO Auto-generated method stub
  int gcd = findGCD(length, dist);
  int set_number = length / gcd;
  for(int i =0; i< gcd; i++){
   int temp = array[i];
   int j = i;
   while((j+gcd) < length){
    array[j] = array[j + gcd];
    j = j + gcd;
   }
   array[j] = temp;
  }
  for (int element : array) {
   System.out.print(element + " ");
  }
 }
 public static void main(String[] args) {
  int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
  leftRotate(array, 11, array.length);
 }
}

Time complexity: O(n)
Auxiliary Space: O(1)

Method 4(The Reversal Algorithm)
Please read this for first three methods of array rotation.

Algorithm:
rotate(arr[], d, n)
  reverse(arr[], 1, d) ;
  reverse(arr[], d + 1, n);
  reverse(arr[], l, n);


Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1]. The idea of the algorithm is:
Reverse A to get ArB. /* Ar is reverse of A */
Reverse B to get ArBr. /* Br is reverse of B */
Reverse all to get (ArBr) r = BA.

For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7
A = [1, 2] and B = [3, 4, 5, 6, 7]
Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7]
Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3]
Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]

Note : Examples and description have been taken from geeksforgeeks.org.

Flowers - greedy

Problem Statement

You and your K−1 friends want to buy N flowers. Flower number i has cost ci. Unfortunately the seller does not want just one customer to buy a lot of flowers, so he tries to change the price of flowers for customers who have already bought some flowers. More precisely, if a customer has already bought x flowers, he should pay (x+1)×ci dollars to buy flower number i. 
You and your K−1 friends want to buy all N flowers in such a way that you spend the least amount of money. You can buy the flowers in any order.

Input:

The first line of input contains two integers N and K(K<=N). The next line contains Nspace separated positive integers c1,c2,...,cN.

Output:

Print the minimum amount of money you (and your friends) have to pay in order to buy all Nflowers.

Constraints

1≤N,K≤100 
Any ci is not more than 106 
Result is guaranteed to be less than 231

Sample input #00

3 3
2 5 6

Sample output #00

13

Sample input #01

3 2
2 5 6

Sample output #01

15

Explanation : 
Sample Case #00: In this example, all of you should buy one flower each. Hence, you'll have to pay 13 dollars. 
Sample Case #01: Here one of the friend buys first two flowers in decreasing order of their price. So he will pay (0+1)*5 + (1+1)*2 = 9. And other friend will buy the costliest flower of cost 6. So total money need is 9+6=15.

Copyright © 2015 HackerRank.
All Rights Reserved

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) throws IOException{
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] in = s.split(" ");
        int n = Integer.parseInt(in[0]);
        int k = Integer.parseInt(in[1]);
        s = br.readLine();
        String[] tmp = s.split(" ");
        int[] cost = new int[n];
        for(int i = 0 ; i < n ; i++)
            {
            cost[i] = Integer.parseInt(tmp[i]);
        }
        Arrays.sort(cost);
        int index = 0, total = 0, j = 1;
        for(int i = n - 1 ; i >= 0 ; i--)
            {
            if(j > k)
            {    
                j = 1;
                index++;
            }
            total += (index + 1) * cost[i];
            j++;  
        }
        System.out.println(total);
    }
}