Like sorting algorithms, binary tree implementation is another good programming exercise. In particular, methods for traversing a tree, searching nodes in a binary search tree and many other binary tree operations form a great recipe for refreshing one’s programming skills. Appended is an implementation of a pretty comprehensive set of binary tree (and binary search tree) operations in Java.
Iterative and recursive methods for each of the operations are developed and grouped in two separate classes, BinTreeI and BinTreeR. In general, most operations are easier to be implemented using recursive methods. For instance, calculating tree height using iterative method is a rather non-trivial exercise whereas it’s almost an one-liner using recursion. Some of the operations such as searching and inserting a tree node are only applicable to binary search tree (BST), for which in-order tree traversal should be used. For generality, pre-order and post-order traversal methods are also included in the code.
Similar to the implementation of sorting algorithms in a previous blog, Java Generics and Comparable interface are used. If wanted, the underlying tree node could be further expanded to contain more complex node data such as map entries (e.g. with class type <Key extends Comparable<Key>, Value>, and Map.Entry<K,V> data).
Node.java – binary tree node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package bintree; class Node<E extends Comparable<E>> { public E element; public Node left; public Node right; public Node() { this(null); } public Node(E e) { element = e; left = null; right = null; } boolean isLeaf() { return (left == null && right == null); } public void printNode() { if (isLeaf()) System.out.print(element + "* -> "); else System.out.print(element + " -> "); } } |
BinTree.java – base binary tree class
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
package bintree; import java.util.LinkedList; // BinTree interface @SuppressWarnings({"unchecked"}) abstract class BinTree<E extends Comparable<E>> { public Node root; public BinTree() { root = null; } public BinTree(E e) { root = new Node(e); } public boolean isEmpty() { return root == null; } public void addLeft(Node currNode, E e) { // CAUTION: this method overwrites left subtree, if exists currNode.left = new Node(e); } public void addRight(Node currNode, E e) { // CAUTION: this method overwrites right subtree, if exists currNode.right = new Node(e); } public void removeLeft(Node currNode) { if (currNode.left != null) { currNode.left = null; } } public void removeRight(Node currNode) { if (currNode.right != null) { currNode.right = null; } } // Search the subtree under the current node for matching data // (Applicable to Binary Search Tree only) public abstract boolean search(Node currNode, E e); // Insert a node into the subtree under the current node // (Applicable to Binary Search Tree only) public abstract void insert(Node currNode, E e); // Delete the first node found with matching data by replacing it with the // max-value node in the branch to the left of the found node // (Applicable to Binary Search Tree only) public abstract boolean deleteFirst(Node currNode, E e); public abstract int size(Node currNode); public abstract int height(Node currNode); public Node rotateLeft(Node currNode) { Node tempNode = currNode.right; currNode.right = tempNode.left; tempNode.left = currNode; return tempNode; // New root node } public Node rotateRight(Node currNode) { Node tempNode = currNode.left; currNode.left = tempNode.right; tempNode.right = currNode; return tempNode; // New root node } // In-order traversal public abstract void traverseIn(Node currNode); // Pre-order traversal public abstract void traversePre(Node currNode); // Post-order traversal public abstract void traversePost(Node currNode); public void printNodeEnd() { System.out.println("(end)"); } } |
BinTreeR.java – binary tree class using recursive methods
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 |
package bintree; import java.util.LinkedList; // BinTree class using recursive methods @SuppressWarnings({"unchecked"}) class BinTreeR<E extends Comparable<E>> extends BinTree<E> { public Node root; public BinTreeR() { super(); } public BinTreeR(E e) { super(e); } public boolean isEmpty() { return super.isEmpty(); } public void addLeft(Node currNode, E e) { super.addLeft(currNode, e); } public void addRight(Node currNode, E e) { super.addRight(currNode, e); } public void removeLeft(Node currNode) { super.removeLeft(currNode); } public void removeRight(Node currNode) { super.removeRight(currNode); } // Search the subtree under the current node for matching data // (Applicable to Binary Search Tree only) public boolean search(Node currNode, E e) { if (currNode == null) { return false; } else { if (((Comparable) e).compareTo(currNode.element) == 0) { return true; } else { if (((Comparable) e).compareTo(currNode.element) < 0) return search(currNode.left, e); else return search(currNode.right, e); } } } // Insert a node into the subtree under the current node // (Applicable to Binary Search Tree only) public void insert(Node currNode, E e) { if (currNode == null) // Do nothing if the input node is null return; if (((Comparable) e).compareTo(currNode.element) <= 0) { if (currNode.left == null) currNode.left = new Node(e); else insert(currNode.left, e); } else { if (currNode.right == null) currNode.right = new Node(e); else insert(currNode.right, e); } } // Delete the first node found with matching data in the subtree under the current node // by replacing it with the max-value node in the branch to the left of the found node // (Applicable to Binary Search Tree only) public boolean deleteFirst(Node currNode, E e) { return deleteFirst(currNode, null, true, e); } // deleteFirst helper recursive method carrying parentNode public boolean deleteFirst(Node currNode, Node parentNode, boolean onLeft, E e) { if (currNode == null) { return false; } else { if (((Comparable) e).compareTo(currNode.element) == 0) { if (currNode.left == null) { if (onLeft) parentNode.left = currNode.right; else parentNode.right = currNode.right; } else if (currNode.right == null) { if (onLeft) parentNode.left = currNode.left; else parentNode.right = currNode.left; } else { // currNode takes data of maxNode on currNode's left branch and remove maxNode Node maxNode = currNode.left; Node maxNodeParent = currNode; if (maxNode.right == null) { currNode.element = maxNode.element; maxNodeParent.left = maxNode.left; } else { while (maxNode.right != null) { maxNodeParent = maxNode; maxNode = maxNode.right; } currNode.element = maxNode.element; maxNodeParent.right = null; } } return true; } else { if (((Comparable) e).compareTo(currNode.element) < 0) { onLeft = true; return deleteFirst(currNode.left, currNode, onLeft, e); } else { onLeft = false; return deleteFirst(currNode.right, currNode, onLeft, e); } } } } public int size(Node currNode) { if (currNode == null) return 0; else return (size(currNode.left) + size(currNode.right) + 1); } public int height(Node currNode) { if (currNode == null) return -1; else return (Math.max(height(currNode.left), height(currNode.right)) + 1); } public Node rotateLeft(Node currNode) { return super.rotateLeft(currNode); } public Node rotateRight(Node currNode) { return super.rotateRight(currNode); } // In-order traversal (recursive) public void traverseIn(Node currNode) { if(currNode == null) { return; } else { traverseIn(currNode.left); currNode.printNode(); traverseIn(currNode.right); } } // Pre-order traversal (recursive) public void traversePre(Node currNode) { if(currNode == null) { return; } else { currNode.printNode(); traversePre(currNode.left); traversePre(currNode.right); } } // Post-order traversal (recursive) public void traversePost(Node currNode) { if(currNode == null) { return; } else { traversePost(currNode.left); traversePost(currNode.right); currNode.printNode(); } } public void printNodeEnd() { super.printNodeEnd(); } } |
BinTreeI.java – binary tree class using iterative methods
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 |
package bintree; import java.util.LinkedList; // BinTree class using iterative methods @SuppressWarnings({"unchecked"}) class BinTreeI<E extends Comparable<E>> extends BinTree<E> { public Node root; public BinTreeI() { super(); } public BinTreeI(E e) { super(e); } public boolean isEmpty() { return super.isEmpty(); } public void addLeft(Node currNode, E e) { super.addLeft(currNode, e); } public void addRight(Node currNode, E e) { super.addRight(currNode, e); } public void removeLeft(Node currNode) { super.removeLeft(currNode); } public void removeRight(Node currNode) { super.removeRight(currNode); } // Search the subtree under the current node for matching data // (Applicable to Binary Search Tree only) public boolean search(Node currNode, E e) { if (currNode == null) return false; while (currNode != null) { if (((Comparable) e).compareTo(currNode.element) == 0) { return true; } else { if (((Comparable) e).compareTo(currNode.element) < 0) { currNode = currNode.left; } else { currNode = currNode.right; } } } return false; } // Insert a node into the subtree under the current node // (Applicable to Binary Search Tree only) public void insert(Node currNode, E e) { if (currNode == null) // Do nothing if the input node is null return; while (currNode != null) { if (((Comparable) e).compareTo(currNode.element) <= 0) { if (currNode.left != null) currNode = currNode.left; else { currNode.left = new Node(e); break; } } else { if (currNode.right != null) currNode = currNode.right; else { currNode.right = new Node(e); break; } } } } // Delete the first node found with matching data in the subtree under the current node // by replacing it with the max-value node in the branch to the left of the found node // (Applicable to Binary Search Tree only) public boolean deleteFirst(Node currNode, E e) { if (currNode == null) // Do nothing if the input node is null return false; boolean onLeft = true; Node parentNode = null; // Search for the first node with matching data while (currNode != null) { if (((Comparable) e).compareTo(currNode.element) == 0) { break; } else { parentNode = currNode; if (((Comparable) e).compareTo(currNode.element) < 0) { onLeft = true; currNode = currNode.left; } else { onLeft = false; currNode = currNode.right; } } } if (currNode == null) { // No node with matching data return false; } else { if (currNode.left == null) { // Remove currNode if (onLeft) parentNode.left = currNode.right; else parentNode.right = currNode.right; } else if (currNode.right == null) { // Remove currNode if (onLeft) parentNode.left = currNode.left; else parentNode.right = currNode.left; } else { // currNode takes data of maxNode on currNode's left branch and remove maxNode Node maxNode = currNode.left; Node maxNodeParent = currNode; if (maxNode.right == null) { currNode.element = maxNode.element; maxNodeParent.left = maxNode.left; } else { while (maxNode.right != null) { maxNodeParent = maxNode; maxNode = maxNode.right; } currNode.element = maxNode.element; maxNodeParent.right = null; } } } return true; } // Calculate tree size using in-order traversal logic public int size(Node currNode) { LinkedList<Node> stack = new LinkedList<Node>(); int nodeCount = 0; while (currNode != null || !stack.isEmpty()) { if (currNode != null) { stack.push(currNode); currNode = currNode.left; } else { currNode = stack.pop(); nodeCount++; currNode = currNode.right; } } return nodeCount; } // Calculate tree height using post-order traversal logic public int height(Node currNode) { LinkedList<Node> stack = new LinkedList<Node>(); Node prevNode = null; int maxCount = 0; if (currNode == null) return -1; stack.push(currNode); while (!stack.isEmpty()) { currNode = stack.peek(); // Traversing down the tree from left or right if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) { if (currNode.left != null) stack.push(currNode.left); else if (currNode.right != null) stack.push(currNode.right); } // Traversing up the tree from the left else if (currNode.left == prevNode) { if (currNode.right != null) stack.push(currNode.right); } // Traversing up the tree from the right, at a leaf node or otherwise else { currNode = stack.pop(); } prevNode = currNode; if (stack.size() > maxCount) maxCount = stack.size(); } return maxCount - 1; } public Node rotateLeft(Node currNode) { return super.rotateLeft(currNode); } public Node rotateRight(Node currNode) { return super.rotateRight(currNode); } // In-order traversal public void traverseIn(Node currNode) { LinkedList<Node> stack = new LinkedList<Node>(); while (currNode != null || !stack.isEmpty()) { if (currNode != null) { stack.push(currNode); currNode = currNode.left; } else { currNode = stack.pop(); currNode.printNode(); currNode = currNode.right; } } printNodeEnd(); } // Pre-order traversal public void traversePre(Node currNode) { LinkedList<Node> stack = new LinkedList<Node>(); while (currNode != null || !stack.isEmpty()) { if (currNode != null) { stack.push(currNode); currNode.printNode(); currNode = currNode.left; } else { currNode = stack.pop(); currNode = currNode.right; } } printNodeEnd(); } // Post-order traversal using a single stack public void traversePost(Node currNode) { LinkedList<Node> stack = new LinkedList<Node>(); Node prevNode = null; if (currNode == null) return; stack.push(currNode); while (!stack.isEmpty()) { currNode = stack.peek(); // Traversing down the tree from left or right if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) { if (currNode.left != null) stack.push(currNode.left); else if (currNode.right != null) stack.push(currNode.right); } // Traversing up the tree from the left else if (currNode.left == prevNode) { if (currNode.right != null) stack.push(currNode.right); } // Traversing up the tree from the right or otherwise else { currNode.printNode(); currNode = stack.pop(); } prevNode = currNode; } printNodeEnd(); } /* // Post-order traversal using two stacks public void traversePost(Node currNode) { LinkedList<Node> inStack = new LinkedList<Node>(); LinkedList<Node> outStack = new LinkedList<Node>(); if (currNode == null) return; inStack.push(currNode); while (!inStack.isEmpty()) { currNode = inStack.pop(); outStack.push(currNode); if (currNode.left != null) inStack.push(currNode.left); if (currNode.right != null) inStack.push(currNode.right); } while (!outStack.isEmpty()) { currNode = outStack.pop(); currNode.printNode(); } printNodeEnd(); } */ public void printNodeEnd() { super.printNodeEnd(); } } |
BinTreeMain.java – test application
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
package bintree; import java.io.*; import java.util.*; class BinTreeMain { @SuppressWarnings({"unchecked"}) public static void main(String[] args) { if (args.length != 1 || !args[0].matches("[iIrR]")) { System.out.println("Usage: java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain I|R (Iterative or Recursive)"); System.out.println(" e.g. java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain R"); System.exit(0); } BinTree tree = null; boolean useRecurMethods = args[0].matches("[rR]"); if (!useRecurMethods) { tree = new BinTreeI(); } else { tree = new BinTreeR(); } /* Tree content (E) / \ / \ (C) (H) / \ / \ (B) (D) (G) (J) / / / (A) (F) (I) / \ (HH) (II) */ tree.root = new Node("E"); // Test insert tree.insert(tree.root, "H"); tree.insert(tree.root, "C"); tree.insert(tree.root, "D"); tree.insert(tree.root, "G"); tree.insert(tree.root, "B"); tree.insert(tree.root, "J"); tree.insert(tree.root, "F"); tree.insert(tree.root, "A"); tree.insert(tree.root, "I"); tree.insert(tree.root, "HH"); tree.insert(tree.root, "II"); // Test search System.out.println("Result: " + (tree.search(tree.root, "G") ? "Found!" : "Not found!")); System.out.println("Result: " + (tree.search(tree.root, "FF") ? "Found!" : "Not found!")); System.out.println("\nTraversing tree from root ..."); tree.traverseIn(tree.root); if (useRecurMethods) tree.printNodeEnd(); System.out.println("\nSize of tree: " + tree.size(tree.root)); System.out.println("Height of tree: " + tree.height(tree.root)); // Test delete System.out.println("\nDeleting first node containing B from root ..."); System.out.println("Result: " + (tree.deleteFirst(tree.root, "B") ? "Found and deleted!" : "Not found!")); System.out.println("\nDeleting first node containing CC from root ..."); System.out.println("Result: " + (tree.deleteFirst(tree.root, "CC") ? "Found and deleted!" : "Not found!")); System.out.println("\nDeleting first node containing H from root ..."); System.out.println("Result: " + (tree.deleteFirst(tree.root, "H") ? "Found and deleted!" : "Not found!")); System.out.println("\nDeleting first node containing J from root ..."); System.out.println("Result: " + (tree.deleteFirst(tree.root, "J") ? "Found and deleted!" : "Not found!")); System.out.println("\nDeleting first node containing E (root node) from root ..."); System.out.println("Result: " + (tree.deleteFirst(tree.root, "E") ? "Found and deleted!" : "Not found!")); System.out.println("Root node now has data " + tree.root.element); System.out.println("\nTraversing tree from root ..."); tree.traverseIn(tree.root); if (useRecurMethods) tree.printNodeEnd(); System.out.println("\nSize of tree: " + tree.size(tree.root)); System.out.println("Height of tree: " + tree.height(tree.root)); } } |