Remove extra edge from BST

Question

I have a BST which looks like below. How can I remove extra edge not needed from BST?

1->2, 1->3, 2->4, 2->5, 3->5

Should remove either 2->5 or 3->5

 void BFS(int s)
    {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];

        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it
        visited[s]=true;
        queue.add(s);

        while (queue.size() != 0)
        {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s+" ");

            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                if (!visited[n])
                {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

Answer 1

What you have is not a tree, it's a Directed Acyclic Graph (DAG):

The algorithm you are looking for is a Spanning Tree Algorithm. One of the simplest ways to find it is to run through your graph depth-first, and mark graph nodes as you find them. If an edge takes you to a node that you have already seen, remove the edge and continue. Once you are done with the depth-first walk, the remaining graph is a tree.

Answer 2

What you want to implement is a self balancing binary tree. An AVL tree is one such. The Wiki page has some well commented pseudo code which should't be terribly difficult to implement in Java.

A web search will reveal plenty of examples.