A binary tree is a data structure composed of nodes. Each node stores a value and references to up to two children (left and right). Binary trees are foundational for many algorithms and structures such as binary search trees (BSTs), heaps, and expression trees. They support operations like traversal (visiting nodes in a specific order), searching, and computing properties like height and size.
The following example shows a general-purpose binary tree with common operations and traversals. It inserts new values in level-order to keep the tree as compact as possible without enforcing any value ordering.
import java.util.*;
class BinaryTree<T> {
static class Node<T> {
T data;
Node<T> left, right;
Node(T data) { this.data = data; }
}
private Node<T> root;
// Height is defined here as number of edges on the longest path.
// For an empty tree: -1; for a single node tree: 0.
public boolean isEmpty() {
return root == null;
}
public void addLevelOrder(T value) {
Node<T> newNode = new Node<>(value);
if (root == null) {
root = newNode;
return;
}
ArrayDeque<Node<T>> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node<T> cur = q.remove();
if (cur.left == null) { cur.left = newNode; return; }
else q.add(cur.left);
if (cur.right == null) { cur.right = newNode; return; }
else q.add(cur.right);
}
}
public int size() { return size(root); }
private int size(Node<T> n) {
return (n == null) ? 0 : 1 + size(n.left) + size(n.right);
}
public int height() { return height(root); }
private int height(Node<T> n) {
if (n == null) return -1;
return 1 + Math.max(height(n.left), height(n.right));
}
public boolean contains(T value) { return contains(root, value); }
private boolean contains(Node<T> n, T value) {
if (n == null) return false;
if (Objects.equals(n.data, value)) return true;
return contains(n.left, value) || contains(n.right, value);
}
public List<T> inorder() {
List<T> out = new ArrayList<>();
inorder(root, out);
return out;
}
private void inorder(Node<T> n, List<T> out) {
if (n == null) return;
inorder(n.left, out);
out.add(n.data);
inorder(n.right, out);
}
public List<T> preorder() {
List<T> out = new ArrayList<>();
preorder(root, out);
return out;
}
private void preorder(Node<T> n, List<T> out) {
if (n == null) return;
out.add(n.data);
preorder(n.left, out);
preorder(n.right, out);
}
public List<T> postorder() {
List<T> out = new ArrayList<>();
postorder(root, out);
return out;
}
private void postorder(Node<T> n, List<T> out) {
if (n == null) return;
postorder(n.left, out);
postorder(n.right, out);
out.add(n.data);
}
public List<T> levelOrder() {
List<T> out = new ArrayList<>();
if (root == null) return out;
ArrayDeque<Node<T>> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node<T> cur = q.remove();
out.add(cur.data);
if (cur.left != null) q.add(cur.left);
if (cur.right != null) q.add(cur.right);
}
return out;
}
public void invert() { root = invert(root); }
private Node<T> invert(Node<T> n) {
if (n == null) return null;
Node<T> left = invert(n.left);
Node<T> right = invert(n.right);
n.left = right;
n.right = left;
return n;
}
public boolean isBalanced() { return checkBalanced(root) != Integer.MIN_VALUE; }
private int checkBalanced(Node<T> n) {
if (n == null) return -1;
int lh = checkBalanced(n.left);
if (lh == Integer.MIN_VALUE) return Integer.MIN_VALUE;
int rh = checkBalanced(n.right);
if (rh == Integer.MIN_VALUE) return Integer.MIN_VALUE;
if (Math.abs(lh - rh) > 1) return Integer.MIN_VALUE; // unbalanced
return 1 + Math.max(lh, rh);
}
}
public class Demo {
public static void main(String[] args) {
BinaryTree<Integer> bt = new BinaryTree<>();
for (int v : new int[]{10, 20, 30, 40, 50, 60}) bt.addLevelOrder(v);
System.out.println(bt.inorder()); // Traversal example
System.out.println(bt.levelOrder()); // BFS order
System.out.println(bt.height()); // Height of the tree
System.out.println(bt.contains(30)); // true
bt.invert();
System.out.println(bt.levelOrder()); // Mirrored
}
}
When you need ordered operations, use a BST. It relies on element comparability to guide search, insert, and delete efficiently.
class BinarySearchTree<T extends Comparable<? super T>> {
static class Node<T> {
T data; Node<T> left, right;
Node(T d) { data = d; }
}
private Node<T> root;
public boolean contains(T value) {
Node<T> cur = root;
while (cur != null) {
int cmp = value.compareTo(cur.data);
if (cmp == 0) return true;
cur = (cmp < 0) ? cur.left : cur.right;
}
return false;
}
public void insert(T value) { root = insert(root, value); }
private Node<T> insert(Node<T> n, T value) {
if (n == null) return new Node<>(value);
int cmp = value.compareTo(n.data);
if (cmp < 0) n.left = insert(n.left, value);
else if (cmp > 0) n.right = insert(n.right, value);
// ignore duplicates or handle as needed
return n;
}
public void remove(T value) { root = remove(root, value); }
private Node<T> remove(Node<T> n, T value) {
if (n == null) return null;
int cmp = value.compareTo(n.data);
if (cmp < 0) n.left = remove(n.left, value);
else if (cmp > 0) n.right = remove(n.right, value);
else {
if (n.left == null) return n.right;
if (n.right == null) return n.left;
// Two children: replace with inorder successor
Node<T> succ = n.right;
while (succ.left != null) succ = succ.left;
n.data = succ.data;
n.right = remove(n.right, succ.data);
}
return n;
}
public List<T> inorder() {
List<T> out = new ArrayList<>();
Deque<Node<T>> st = new ArrayDeque<>();
Node<T> cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) { st.push(cur); cur = cur.left; }
cur = st.pop();
out.add(cur.data);
cur = cur.right;
}
return out; // Sorted order for BST
}
}