Tree Data Structure in Java

Implementation of Tree Data Structure using java

Organizational tree example

What is Binary Search Tree-BST

BST is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

BST example

Basic Operations

1. Insertion/ add node.
2. Traversing: Inorder, Preorder, and Postorder
3. Deletion/delete a node

Node Class

//Node class 
    static class Node{
        //properties of node class
        int data;
        Node leftNode, rightNode;
        //constructor
        Node(int data){
            this.data=data;
            leftNode=rightNode=null;
        }
    }

Insertion/ add node method

Get Rafia Shaikh | Byte School’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Implementation using loop

 public void addNodeL(int data){
        //create new node
        Node newNode=new Node(data); 
        if(isEmpty()){
            root=newNode;
            size++;
            return;
        }
        //temp node
        Node tempNode=root;
        while(true){
            if(data<=tempNode.data){
                if(tempNode.leftNode==null){
                    tempNode.leftNode=newNode;
                    size++;
                    return;
                }
                tempNode=tempNode.leftNode;
            }
            else if(data>=tempNode.data){
                if(tempNode.rightNode==null){
                    tempNode.rightNode=newNode;
                    size++;
                    return;
                }
                tempNode=tempNode.rightNode;
            }
        }
    }

Implementation using recursion

public void addNodeR(Node node, int data){
        Node newNode=new Node(data);
        if(isEmpty()){
            root=newNode;
        }
        else{
            if(data<node.data){
                if(node.leftNode!=null){
                    addNodeR(node.leftNode, data);
                }
                else{
                    node.leftNode=new Node(data);
                }
            }
            else{
                if(node.rightNode!=null){
                    addNodeR(node.rightNode, data);
                }
                else{
                    node.rightNode=newNode;
                }
            }
        }
        size++;
    }

Preorder Traversing

To traverse a nonempty binary tree:

1. Visit the root.
2. If the left subtree is nonempty, do a preorder traversal on it.
3. If the right subtree is nonempty, do a preorder traversal on it.

Preorder traversal of a binary tree

The nodes are visited in the order A, B, D, H, I, E, J, K, C, F, L, M, G, N, O.

    //preorder traverse 
    public void preOrderTraverse(Node node){
        if(node==null)
            return;
        else{
            System.out.println(" "+node.data);
            preOrderTraverse(node.leftNode);
            preOrderTraverse(node.rightNode);
        }
    }

Postorder Traversing

To traverse a nonempty binary tree:

1. If the left subtree is nonempty, do a postorder traversal on it.
2. If the right subtree is nonempty, do a postorder traversal on it.
3. Visit the root.

Postorder traversal of a binary tree

The nodes are visited in the order H, I, D, J, K, E, B, L, M, F, N, O, G, C, A.

 //postorder traverse 
    public void postOrderTraverse(Node node){
        if(node==null)
            return;
        else{
            postOrderTraverse(node.leftNode);
            postOrderTraverse(node.rightNode);
            System.out.println(" "+node.data);
        }
    }
}

Inorder Traversing

To traverse a nonempty binary tree:

1. If the left subtree is nonempty, do a preorder traversal on it.
2. visit the root.
3. If the right subtree is nonempty, do a preorder traversal on it.

Inorder traversal of a binary tree

The nodes are visited in the order H, D, I, B, J, E, K, A, L, F, M, C, N, G, O.

//inorder traverse 
    public void inOrderTraverse(Node node){
        if(node==null)
            return;
        else{
            inOrderTraverse(node.leftNode);
            System.out.println(" "+node.data);
            inOrderTraverse(node.rightNode);
        }
    }

Complete Code

GitHub - Rafia-Shaikh-eng/Data-Structures-and-Algorithms-in-Java: Basic and advance tutorials of…

Recorded Lecture

Rafia Shaikh — YouTube

Photo by Luca Bravo on Unsplash