Binary Tree in Java using OOP concepts and Generics

In this article at OpenGenus, we will implement Binary Tree data structure in Java Programming Language using OOP concepts and Generics.

Table of Contents

1. Introduction
2. Code Explanation
3. Implementation
4. Benefits of using Generics

Introduction:

A binary tree consists of nodes connected in a hierarchical structure. Each node has at most two child nodes, referred to as the left child and the right child. The topmost node in a binary tree is called the root node. The left child of a node has a smaller value (in terms of a defined comparison) than the parent node, while the right child has a larger value. This ordering property makes binary trees useful for efficient search, insertion, and deletion operations.

Generics in programming languages, including Java, provide a way to create reusable code that can work with different types of data. It allows you to define classes, interfaces, and methods that can be parameterized with type information.This enhances code reusability, type safety, and can help avoid casting and potential type errors at runtime.

Code Explanation

In this section, we will explain all the building blocks of the code including BinaryTreeNode class creation, the main logic of Inorder Implementation along with insertion of values.

Create a binary Node

First, we need to define BinaryTreeNode class. The BinaryTreeNode class defines a single node in a binary tree. It is a generic class with a type parameter T that extends Comparable<T>, allowing nodes to hold any data type that can be compared. Each node has a data field to store the value, and left and right fields to reference the left and right child nodes respectively. The constructor initializes the node with the provided data and sets the child references to null.

// BinaryTreeNode class represents a single node in the binary tree
    
class BinaryTreeNode<T extends Comparable<T>> {
    T data;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    public BinaryTreeNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

The BinaryTree class represents a binary tree and provides operations to manipulate the tree. It also uses a generic type T that extends Comparable<T>. The class has a root field to store the reference to the root node. The constructor initializes the tree with a null root.

The Main Logic
The insert method inserts a new node with the provided data into the binary tree. It calls the private insertRecursive method, which is a recursive helper function. It compares the data with the current node's data and recursively inserts the data into the left or right subtree accordingly.

The inorderTraversal method performs an in-order traversal of the binary tree, printing the node values in ascending order. It calls the private inorderRecursive method, which recursively traverses the tree in the in-order fashion: left subtree, current node, right subtree.

// BinaryTree class represents the binary tree and provides various operations
    
class BinaryTree<T extends Comparable<T>> {
    BinaryTreeNode<T> root;

    public BinaryTree() {
        this.root = null;
    }

    // Method to insert a new node in the binary tree
    public void insert(T data) {
        this.root = insertRecursive(this.root, data);
    }

    private BinaryTreeNode<T> insertRecursive(BinaryTreeNode<T> currentNode, T data) {
        if (currentNode == null) {
            return new BinaryTreeNode<>(data);
        }

        if (data.compareTo(currentNode.data) < 0) {
            currentNode.left = insertRecursive(currentNode.left, data);
        } else if (data.compareTo(currentNode.data) > 0) {
            currentNode.right = insertRecursive(currentNode.right, data);
        }

        return currentNode;
    }

    // Method to perform an in-order traversal of the binary tree
    public void inorderTraversal() {
        inorderRecursive(this.root);
    }

    private void inorderRecursive(BinaryTreeNode<T> currentNode) {
        if (currentNode != null) {
            inorderRecursive(currentNode.left);
            System.out.print(currentNode.data + " ");
            inorderRecursive(currentNode.right);
        }
    }
}

Inserting values
In this following implementation, we will deal with Integers only, but it can be used for any primitive data type or user-defined datatype.

    // Example usage
public class Main {
    public static void main(String[] args) {
        BinaryTree<Integer> binaryTree = new BinaryTree<>();
        binaryTree.insert(5);
        binaryTree.insert(3);
        binaryTree.insert(7);
        binaryTree.insert(1);
        binaryTree.insert(4);

        System.out.println("In-order traversal of the binary tree:");
        binaryTree.inorderTraversal();
    }
}

Examples with different data types:

BinaryTree<String> stringTree = new BinaryTree<>();
stringTree.insert("apple");
stringTree.insert("banana");
stringTree.insert("orange");
stringTree.insert("mango");

System.out.println("In-order traversal of the string binary tree:");
stringTree.inorderTraversal();

Here, we create an instance of BinaryTree with a generic type of String. We insert several strings into the tree and perform an in-order traversal.

BinaryTree<Double> doubleTree = new BinaryTree<>();
doubleTree.insert(3.14);
doubleTree.insert(1.23);
doubleTree.insert(2.5);
doubleTree.insert(4.7);

System.out.println("In-order traversal of the double binary tree:");
doubleTree.inorderTraversal();

In this example, we create an instance of BinaryTree with a generic type of Double. We insert several double values into the tree and perform an in-order traversal.

You can modify the code and create instances of BinaryTree with other data types as per your requirements.

Implementation:

In Java, we can create a binary tree using OOP concepts and generics by defining classes for the tree nodes and the tree itself. Here's the implementation:

// BinaryTreeNode class represents a single node in the binary tree
class BinaryTreeNode<T extends Comparable<T>> {
    T data;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    public BinaryTreeNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// BinaryTree class represents the binary tree and provides various operations
class BinaryTree<T extends Comparable<T>> {
    BinaryTreeNode<T> root;

    public BinaryTree() {
        this.root = null;
    }

    // Method to insert a new node in the binary tree
    public void insert(T data) {
        this.root = insertRecursive(this.root, data);
    }

    private BinaryTreeNode<T> insertRecursive(BinaryTreeNode<T> currentNode, T data) {
        if (currentNode == null) {
            return new BinaryTreeNode<>(data);
        }

        if (data.compareTo(currentNode.data) < 0) {
            currentNode.left = insertRecursive(currentNode.left, data);
        } else if (data.compareTo(currentNode.data) > 0) {
            currentNode.right = insertRecursive(currentNode.right, data);
        }

        return currentNode;
    }

    // Method to perform an in-order traversal of the binary tree
    public void inorderTraversal() {
        inorderRecursive(this.root);
    }

    private void inorderRecursive(BinaryTreeNode<T> currentNode) {
        if (currentNode != null) {
            inorderRecursive(currentNode.left);
            System.out.print(currentNode.data + " ");
            inorderRecursive(currentNode.right);
        }
    }
}

// Example usage
public class Main {
    public static void main(String[] args) {
        BinaryTree<Integer> binaryTree = new BinaryTree<>();
        binaryTree.insert(5);
        binaryTree.insert(3);
        binaryTree.insert(7);
        binaryTree.insert(1);
        binaryTree.insert(4);

        System.out.println("In-order traversal of the binary tree:");
        binaryTree.inorderTraversal();
    }
}

In this implementation, the BinaryTreeNode class represents a single node in the binary tree and holds the data and references to the left and right child nodes. The BinaryTree class represents the binary tree itself and provides methods for inserting nodes and performing an in-order traversal. The insert method inserts a new node in the appropriate position based on the comparison of data values. The inorderTraversal method performs an in-order traversal of the tree, which visits the left subtree, then the current node, and finally the right subtree.

The BinaryTreeNode class and the BinaryTree class both use generics with the T type parameter, which extends Comparable. This allows the binary tree to work with various data types that implement the Comparable interface, enabling comparisons between elements.

The example usage in the Main class demonstrates how to create a binary tree object, insert nodes with integer values, and perform an in-order traversal.

Benefits of generics include:

Code Reusability: Generics enable the creation of generic classes and methods that can be used with different types, reducing code duplication and improving maintainability.

Type Safety: By parameterizing the types, generics provide compile-time type checking, reducing the chances of type-related errors at runtime.

Abstraction: Generics allow you to write code that operates on a general level, independent of specific types, promoting more abstract and modular programming.

Performance: Generics do not involve runtime type checking or casting, resulting in efficient and optimized code execution.

Generics are widely used in Java collections frameworks (such as ArrayList, LinkedList, and HashMap), as well as in various other Java APIs and libraries.By leveraging generics, you can create more flexible, reusable, and type-safe code, enabling the development of robust and maintainable applications.

With this article at OpenGenus, you have gained valuable knowledge on implementing Binary Tree in Java using OOP concepts and Generics.