Aug 25, 2013

Creating a binary search tree using recursion in Java

Program for creating binary search tree using recursive method

private void addNode(Node node, int n)
{
    if (n < node.data)
    {
        if (node.left != null)
        {
            addNode(node.left, n);
        }
        else
        {
            node.left = new Node(n);
        }
    }
    else if (n > node.data)
    {
        if (node.right != null)
        {
            addNode(node.right, n);
        }
        else
        {
            node.right = new Node(n);
        }
    }
    else
    {
        System.out.println("WARNING: Number exists already");
    }
}

Below is the complete program and sample execution.
package programs;

public class BST
{
    private class Node
    {
        Node left = null;
        Node right = null;
        int data;

        Node(int n) {
            data = n;
        }
    }

    private Node root = null;

    public BST() {
    }

    /**
     * Adds elements in the tree using recursion
     */
    public void add(int n)
    {
        if (root == null)
        {
            root = new Node(n);
        }
        else
        {
            addNode(root, n);
        }
    }

    private void addNode(Node node, int n)
    {
        if (n < node.data)
        {
            if (node.left != null)
            {
                addNode(node.left, n);
            }
            else
            {
                node.left = new Node(n);
            }
        }
        else if (n > node.data)
        {
            if (node.right != null)
            {
                addNode(node.right, n);
            }
            else
            {
                node.right = new Node(n);
            }
        }
        else
        {
            System.out.println("WARNING: Number exists already");
        }
    }

    public void print()
    {
        inorderPrint(root);
    }

    private void inorderPrint(Node node)
    {
        if (node != null)
        {
            inorderPrint(node.left);
            System.out.print(" [" + node.data + "] ");
            inorderPrint(node.right);
        }
    }
}

Testing the tree with the client program
package programs;

public class Test
{
    public static void main(String[] args)
    {
        BST tree = new BST();
        tree = new BST();
        tree.add(50);
        tree.add(10);
        tree.add(20);
        tree.add(30);
        tree.add(60);
        tree.add(55);
        tree.add(70);

        tree.print();
    }
}

Output

No comments :

Post a Comment