Binary Tree Implementation in Java: Traversal, Creation & Core Operations

Binary Tree Representation

A binary tree node contains an integer data field and references to left and right child nodes. The TreeNode class is defined with a constructor initializing data and setting both children to null.

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

Tree Traversals

Recursive Pre-order Traversal

Visit root, then recursively traverse left subtree, then right subtree.

public void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.println(root.data);
    preOrder(root.left);
    preOrder(root.right);
}

Recursive In-order Traversal

Recursively traverse left subtree, visit root, then recursively traverse right subtree.

public void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    System.out.println(root.data);
    inOrder(root.right);
}

Recursive Post-order Traversal

Recursively traverse left subtree, then right subtree, then visit root.

public void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.println(root.data);
}

Iterative Level-order Traversal

Uses a Queue (implemented with LinkedList) to visit nodes level by level from left to right.

public void levelOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.data);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

Full Binary Tree Creation

Given an array, the method createFullTree recursively builds a full binary tree by selecting the middle element as root, then recursively building left and right subtrees from the left and right subarrays.

public TreeNode createFullTree(int[] arr, int start, int end) {
    if (start > end) {
        return null;
    }
    int mid = (start + end) / 2;
    TreeNode root = new TreeNode(mid + 1);
    root.left = createFullTree(arr, start, mid - 1);
    root.right = createFullTree(arr, mid + 1, end);
    return root;
}

Other Common Methods

Count Nodes

Recursively counts nodes: 0 for null, otherwise 1 plus counts of left and right subtrees.

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return countNodes(root.left) + countNodes(root.right) + 1;
}

Get Tree Height

Recursively computes height as 1 plus the maximum of left and right subtree heights; null returns 0.

public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

Count Leaf Nodes

A leaf has both children null. Recursively sums leaf counts of left and right subtrees; returns 1 for leaf, 0 for null.

public int getLeafCount(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }
    return getLeafCount(root.left) + getLeafCount(root.right);
}

Complete Runnable Example

The article concludes with a full BinaryTreeExample class that creates a full binary tree from an array of seven integers, then invokes all traversal and utility methods, printing results to console. This allows immediate verification of each operation.