Aug 25, 2013

Creating a binary search tree using iterative approach in Java

Program for creating a binary search tree using iterative method

private void addNode(Node node, int n)
{
    while (node != null)
    {
        if(n < node.data)
        {
            if(node.left != null)
            {
                node = node.left;
            }
            else
            {
                node.left = new Node(n);
                return;
            }
        }
        else if(n > node.data)
        {
            if(node.right != null)
            {
                node = node.right;
            }
            else
            {
                node.right = new Node(n);
                return;
            }
        }
        else
        {
            System.out.println("WARNING: Elements are equal");
            return;
        }
    }
}

Below is he 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 element in the tree using iteration
     */
    public void add(int n)
    {
        if (root == null)
        {
            root = new Node(n);
        }
        else
        {
            addNode(root, n);
        }
    }

    private void addNode(Node node, int n)
    {
        while (node != null)
        {
            if(n < node.data)
            {
                if(node.left != null)
                {
                    node = node.left;
                }
                else
                {
                    node.left = new Node(n);
                    return;
                }
            }
            else if(n > node.data)
            {
                if(node.right != null)
                {
                    node = node.right;
                }
                else
                {
                    node.right = new Node(n);
                    return;
                }
            }
            else
            {
                System.out.println("WARNING: Elements are equal");
                return;
            }

        }
    }

    /**
     * for testing purpose
     */
    public void print()
    {
        inorderPrint(root);
    }

    private void inorderPrint(Node node)
    {
        if (node != null)
        {
            inorderPrint(node.left);
            System.out.println(node.data);
            inorderPrint(node.right);
        }
    }
}

Testing the tree using client program
package programs;

public class Test
{
    public static void main(String[] args)
    {
        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