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. |  |
- 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.
n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1
h = O(log n)
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
- 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;
| 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 |  |
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: }
