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
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
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
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
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
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));
}
}