Java Binary Trees

A binary tree is a data structure made of nodes, where each node can have at most two children: a left child and a right child. Binary trees are useful when data has a hierarchy, or when you want search and ordering behavior built around smaller and larger values.

Tree Nodes

A binary tree starts with one top node called the root. Each node stores a value and references to its left and right children. If a child does not exist, the reference is null.

In Java, a simple tree node can be represented with a class that contains three fields: the stored value, the left child, and the right child. The node class is often small because the interesting logic usually lives in methods that walk through the tree.

Binary Search Trees

A common kind of binary tree is a binary search tree, or BST. In a BST, values smaller than a node go on the left, and values larger than a node go on the right. This rule makes it possible to search by choosing one side of the tree at each step.

For example, if the current node stores 5 and you are searching for 7, you only need to continue into the right side. If you are searching for 2, you continue into the left side.

Traversing a Tree

To traverse a tree means to visit its nodes in a chosen order. One useful traversal for a binary search tree is in-order traversal:

1. Visit the left subtree.
2. Visit the current node.
3. Visit the right subtree.

For a binary search tree, in-order traversal prints the values from smallest to largest.

Example

This program builds a small binary search tree, prints it in sorted order, searches for two values, and calculates the tree height.

public class Main {
    static class Node {
        int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }

    static void appendInOrder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }

        appendInOrder(node.left, result);

        if (result.length() > 0) {
            result.append(" ");
        }
        result.append(node.value);

        appendInOrder(node.right, result);
    }

    static boolean contains(Node node, int target) {
        if (node == null) {
            return false;
        }

        if (node.value == target) {
            return true;
        }

        if (target < node.value) {
            return contains(node.left, target);
        }

        return contains(node.right, target);
    }

    static int height(Node node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        return 1 + Math.max(leftHeight, rightHeight);
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(7);
        root.left.right = new Node(4);
        root.right.right = new Node(9);

        StringBuilder values = new StringBuilder();
        appendInOrder(root, values);

        System.out.println("In-order traversal: " + values);
        System.out.println("Contains 7: " + contains(root, 7));
        System.out.println("Contains 3: " + contains(root, 3));
        System.out.println("Height: " + height(root));
    }
}

Output:

In-order traversal: 2 4 5 7 9
Contains 7: true
Contains 3: false
Height: 3

How It Works

The program creates five nodes. The root stores 5. Smaller values are placed on the left side, and larger values are placed on the right side, so the tree follows the binary search tree rule.

The appendInOrder() method uses recursion. It first handles the left side, then adds the current value, then handles the right side. Because this tree is a BST, that produces sorted output.

The contains() method also uses recursion, but it does not visit every node unless it has to. If the target is smaller than the current value, it searches left. If the target is larger, it searches right. When it reaches null, the value was not found.

The height() method returns the number of levels in the tree. An empty tree has height 0. A single node has height 1. This example has three levels, so its height is 3.

Why Balance Matters

A binary search tree is fastest when its values are spread across both sides. If values are inserted in sorted order, the tree can become a long chain, which makes searching closer to searching through a list. Later data structures, such as balanced trees, solve this by keeping the tree height under control.

Takeaway: a binary tree stores data in linked nodes, and recursive methods are a natural way to traverse, search, and measure it.