Search code examples
linked-listbinary-search-tree

BST to Linked list


Can anyone suggest an algorithm to convert a Binary Search Tree to a singly linked list. Also note that at each step of conversion the highest values node in the list should point to the smallest valued node in the list.


Solution

  • if(!tree.isEmpty())
    {   
        Node node1 = tree.removeMin();
        Node node2;
        Node currentNode;
        Node temp;
        if(!tree.isEmpty())
        {
            node2 = tree.removeMax();
            node2.setNext(node1);
            currentNode = node2;
            while(!tree.isEmpty())
            {
                temp = tree.removeMin();
                temp.setNext(currentNode);
                currentNode = temp;
            }
        }
        Node head = temp;
    }
    

    This conforms to a singly linked list and the maximum value in the list always points to the least value in the list. No other qualifications were given.