Java Program to Implement Binary Tree

May 19, 2023

What is a Binary Tree?

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Each node in a binary tree has a value and a pointer to the left and right child nodes. The topmost node in a binary tree is called the root. The left subtree of a node contains only nodes with keys lesser than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key. The leaves of a binary tree, which have no children, are often used to represent the end of a sequence of operations or data.

Steps to Implement Binary Tree Data Structure :

1. Define a class Node that will represent each node in the tree. The class should have the following properties:

1. An integer value to store the key or data of the node

2. A pointer to the left child node

3. A pointer to the right child node

 class Node {
     int key;
     Node left, right;
     
     public Node(int item) {
         key = item;
         left = right = null;
     }
 }

2. Define a class BinaryTree that will represent the binary tree as a whole. The class should have the following properties:

A pointer to the root node
Methods for inserting new nodes into the tree
Methods for traversing the tree in different ways (e.g. in-order, pre-order, post-order)

 class BinaryTree {
     Node root;

     BinaryTree() {
         root = null;
     }

3. Implement the insert method in the BinaryTree class.

This method should take in an integer value (the key of the new node) and insert it into the tree in the appropriate location. You can implement this method using a recursive helper function called insertRec. This helper function should take in the current root node and the key to be inserted, and return the updated root node after the insertion.

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

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

4. Implement the inorder method in the BinaryTree class.

This method should traverse the tree in an in-order fashion (i.e. visiting the left subtree, then the node itself, then the right subtree) and print out the key of each node. You can implement this method using a recursive helper function called inorderRec. This helper function should take in the current root node and traverse the left subtree, the root node itself, and the right subtree recursively.

void inorder() {
    inorderRec(root);
}

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

5. Create an instance of the BinaryTree class and insert elements in the tree by calling

    BinaryTree tree = new BinaryTree(); 
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);

Implementation of Binary Data Structure in Java :

class Node {
    int key;
    Node left, right;

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

class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

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

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

    void inorder() {
        inorderRec(root);
    }

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

Explanation : This implementation uses a class Node to represent each node in the tree, which has an integer value and pointers to the left and right children. The BinaryTree class has a root field that keeps track of the topmost node of the tree. It has methods for inserting new nodes into the tree, and for traversing the tree in an in-order fashion (i.e. visiting the left subtree, then the node itself, then the right subtree).

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others