Leave a comment

Convert a binary search tree to sorted list

Ques: You have given a binary search tree and you need to change this tree to link list that contains nodes in sorted order.

Solution: We all know that smaller values are on left side. So we need to keep left side values at first place for sorted list. To make this happen we will perform a left ->right rotation starting from root. As we will start from root, after each rotation we will check if still there is a left child, if yes we will again perform a rotation and if not we will jump to the right child and perform the same algorithm as we did with root. Let’s consider the example given below:

one

So in the given tree we start from root, we can see left child is there so will perform a left to right rotation and tree becomes like this:
two

Now the root is 6. Again we can see the left of root is present so again we can perform left->right rotation and after rotation 5 will be the root of the tree. As 5 became root there is no more node in the left side of root then we will jump to the right of root which is node 6. This node has no left child so will move to right of this node which is node 8 and it has left child so will perform a left->right rotation.

three

As we rotate at node with label 8, we can clearly see that the parent of node with label 7 has been changed from 8 to 6 so we have to keep track of parent of node while jumping to the right child. This way final rotation will be at node 10. So, final list will be sorted and will look like this:

     5--6--7--8--9--10--11

Look at the below given code:

public class BST{
    private int val;
    private BST left;
    private BST right;
    public BST(int val){
        this.val = val;
    }
    //assume getters and setters are here for each field
}
public class BSTUtills{
    public BST convertBstToSortedList(BST root) {
    BST par = null;
    if(root != null) {
        while(root != null){
            while(root.getLeft() != null) {
                //perform left->right rotation
                BST temp = root.getLeft();
                root.setLeft(temp.getRight());
                temp.setRight(root);
                root = temp;
                if(par != null)
                    par.setRight(root);
            }
            par = root;
            root = root.getRight();
            }
    }
    return root;
    }
}

Time Complexity: As you can see that we are visiting all nodes maximum one time so the time complexity is O(n).

Space Complexity: We did not take any extra space so space complexity is O(1).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: