Building a Binary Tree Program in Java

Binary trees are a fundamental data structure in computer science, often used to implement efficient searching and sorting algorithms. Let’s explore how to build, traverse, and search within a binary tree.

Introduction to Binary Trees
Binary Tree Node Definition
Binary Tree Class
Main Class: Putting It All Together
Complete Code
Conclusion

Introduction to Binary Trees

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. Here’s a visual representation of a simple binary tree:

        50
       /  \
     30    70
    /  \   / \
   20  40 60 80

We will build a binary tree in Java and implement various operations such as insertion, in-order, pre-order, post-order traversal, and searching.

Binary Tree Node Definition

Let’s start by defining a node in the binary tree.

class Node {
    int data;
    Node left;
    Node right;

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

Here, each node contains:

An integer data.
References to the left and right child nodes.

Binary Tree Class

The BinaryTree class encapsulates the structure and operations of the binary tree.

Insert Method

To insert a new node into the tree:

class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);

        return root;
    }
}

Traversal Methods

We can traverse the binary tree in different orders:

In-order Traversal:

void inorder() {
    inorderRec(root);
}

void inorderRec(Node root) {
    if (root != null) {
        inorderRec(root.left);
        System.out.print(root.data + " ");
        inorderRec(root.right);
    }
}

Pre-order Traversal:

void preorder() {
    preorderRec(root);
}

void preorderRec(Node root) {
    if (root != null) {
        System.out.print(root.data + " ");
        preorderRec(root.left);
        preorderRec(root.right);
    }
}

Post-order Traversal:

void postorder() {
    postorderRec(root);
}

void postorderRec(Node root) {
    if (root != null) {
        postorderRec(root.left);
        postorderRec(root.right);
        System.out.print(root.data + " ");
    }
}

Search Method

To search for a specific value:

boolean search(int data) {
    return searchRec(root, data) != null;
}

Node searchRec(Node root, int data) {
    if (root == null || root.data == data)
        return root;

    if (root.data > data)
        return searchRec(root.left, data);

    return searchRec(root.right, data);
}

Main Class: Putting It All Together

Now, let’s see how to use the BinaryTree class in a main program.

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // Insert elements
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // Print in-order traversal
        System.out.print("Inorder traversal: ");
        tree.inorder();
        System.out.println();

        // Print pre-order traversal
        System.out.print("Preorder traversal: ");
        tree.preorder();
        System.out.println();

        // Print post-order traversal
        System.out.print("Postorder traversal: ");
        tree.postorder();
        System.out.println();

        // Search for an element
        int key = 40;
        if (tree.search(key))
            System.out.println("Element " + key + " found in the tree");
        else
            System.out.println("Element " + key + " not found in the tree");
    }
}

Complete Code

Here’s the complete code for the binary tree implementation in Java:

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);

        return root;
    }

    void inorder() {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    void preorder() {
        preorderRec(root);
    }

    void preorderRec(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preorderRec(root.left);
            preorderRec(root.right);
        }
    }

    void postorder() {
        postorderRec(root);
    }

    void postorderRec(Node root) {
        if (root != null) {
            postorderRec(root.left);
            postorderRec(root.right);
            System.out.print(root.data + " ");
        }
    }

    boolean search(int data) {
        return searchRec(root, data) != null;
    }

    Node searchRec(Node root, int data) {
        if (root == null || root.data == data)
            return root;

        if (root.data > data)
            return searchRec(root.left, data);

        return searchRec(root.right, data);
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.print("Inorder traversal: ");
        tree.inorder();
        System.out.println();

        System.out.print("Preorder traversal: ");
        tree.preorder();
        System.out.println();

        System.out.print("Postorder traversal: ");
        tree.postorder();
        System.out.println();

        int key = 40;
        if (tree.search(key))
            System.out.println("Element " + key + " found in the tree");
        else
            System.out.println("Element " + key + " not found in the tree");
    }
}

Conclusion

This post has covered the basics of implementing a binary tree in Java, including how to insert nodes, perform different types of traversals, and search for nodes. Binary trees are versatile and form the basis for many complex data structures and algorithms.