Binary Tree Program in Java

In this post, we will write a Java program to implement a Binary tree.

A binary tree is a recursive data structure where each node can have 2 children at most.

A common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree.

Binary Tree Program in Java

Here is the Binary tree program to implement a sorted binary tree in Java, and its most common operations.

``````package com.java.collections;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {

Node root;

public void add(int value) {
root = addRecursive(root, value);
}

private Node addRecursive(Node current, int value) {

if (current == null) {
return new Node(value);
}

if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
}

return current;
}

public boolean isEmpty() {
return root == null;
}

public int getSize() {
return getSizeRecursive(root);
}

private int getSizeRecursive(Node current) {
return current == null ? 0 : getSizeRecursive(current.left) + 1 + getSizeRecursive(current.right);
}

public boolean containsNode(int value) {
return containsNodeRecursive(root, value);
}

private boolean containsNodeRecursive(Node current, int value) {
if (current == null) {
return false;
}

if (value == current.value) {
return true;
}

return value < current.value
? containsNodeRecursive(current.left, value)
: containsNodeRecursive(current.right, value);
}

public void delete(int value) {
root = deleteRecursive(root, value);
}

private Node deleteRecursive(Node current, int value) {
if (current == null) {
return null;
}

if (value == current.value) {
// Case 1: no children
if (current.left == null && current.right == null) {
return null;
}

// Case 2: only 1 child
if (current.right == null) {
return current.left;
}

if (current.left == null) {
return current.right;
}

// Case 3: 2 children
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}

current.right = deleteRecursive(current.right, value);
return current;
}

private int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}

public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
visit(node.value);
traverseInOrder(node.right);
}
}

public void traversePreOrder(Node node) {
if (node != null) {
visit(node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}

public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
visit(node.value);
}
}

public void traverseLevelOrder() {
if (root == null) {
return;
}

Queue<Node> nodes = new LinkedList<>();
nodes.add(root);

while (!nodes.isEmpty()) {

Node node = nodes.remove();

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

if (node.left != null) {
nodes.add(node.left);
}

if (node.left != null) {
nodes.add(node.right);
}
}
}

public void traverseInOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node current = root;
stack.push(root);
while(! stack.isEmpty()) {
while(current.left != null) {
current = current.left;
stack.push(current);
}
current = stack.pop();
visit(current.value);
if(current.right != null) {
current = current.right;
stack.push(current);
}
}
}

public void traversePreOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node current = root;
stack.push(root);
while(! stack.isEmpty()) {
current = stack.pop();
visit(current.value);

if(current.right != null)
stack.push(current.right);

if(current.left != null)
stack.push(current.left);
}
}

public void traversePostOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node prev = root;
Node current = root;
stack.push(root);

while (!stack.isEmpty()) {
current = stack.peek();
boolean hasChild = (current.left != null || current.right != null);
boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null));

if (!hasChild || isPrevLastChild) {
current = stack.pop();
visit(current.value);
prev = current;
} else {
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
}

private void visit(int value) {
System.out.print(" " + value);
}

class Node {
int value;
Node left;
Node right;

Node(int value) {
this.value = value;
right = null;
left = null;
}
}

public static void main(String arg[]){
BinaryTree bt = new BinaryTree();

bt.add(6);
bt.add(4);
bt.add(8);
bt.add(3);
bt.add(5);
bt.add(7);
bt.add(9);

bt.traversePostOrder(bt.root);
System.out.println();
bt.traversePostOrderWithoutRecursion();

bt.traverseInOrder(bt.root);
System.out.println();
bt.traverseInOrderWithoutRecursion();

bt.traversePreOrder(bt.root);
System.out.println();
bt.traversePreOrderWithoutRecursion();

bt.traverseLevelOrder();

}
}
``````

Output:

`````` 3 5 4 7 9 8 6
3 5 4 7 9 8 6 3 4 5 6 7 8 9
3 4 5 6 7 8 9 6 4 3 5 8 7 9
6 4 3 5 8 7 9 6 4 8 3 5 7 9``````