Question 75 : Convert sorted Linked List to balanced BST

In this post, we will see how to convert sorted LinkedList to a balanced binary search tree.

There are two ways to do it.

Solution 1:

It is very much similar to convert sorted array to BST. Find middle element of linked list and make it root and do it recursively.

Time complexity : o(nlogn).

Solution 2:

This solution will follow bottom up approach rather than top down.

• We need to find length of linked list
• We will first create left subtree recursively using n/2 nodes.
• We will create root node and connect left subtree to the root node.
• Similarly create right subtree recursively and connect root to right subtree.

Java Program to convert sorted LinkedList to balanced BST:

public class SortedLinkedListToBSTMain {

    private Node head;

    private static class Node {
        private int value;
        private Node next;

        Node(int value) {
            this.value = value;

        }
    }

    public static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int data) {
            this.data = data;
        }
    }

    public static void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void addToTheLast(Node node) {

        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;

            temp.next = node;
        }
    }

    public void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }

    // Find length of linked list using iterative method
    public int lengthOfLinkedList() {
        Node temp = head;
        int count = 0;
        while (temp != null) {
            temp = temp.next;
            count++;
        }
        return count;
    }

    public TreeNode convertSortedLinkedListToBST(int n) {
        /* Base Case for recursion*/
        if (n <= 0)
            return null;

        /* Recursively creating the left subtree */
        TreeNode left = convertSortedLinkedListToBST(n / 2);

        /* Create a root node*/
        TreeNode root = new TreeNode(head.value);

        // Set pointer to left subtree
        root.left = left;
        head = head.next;
        /* Create right subtree with remaining nodes*/
        root.right = convertSortedLinkedListToBST(n - n / 2 - 1);

        return root;
    }
    public static void main(String[] args) {
        SortedLinkedListToBSTMain list = new SortedLinkedListToBSTMain();
        // Creating a linked list
        Node head = new Node(10);
        list.addToTheLast(head);
        list.addToTheLast(new Node(20));
        list.addToTheLast(new Node(30));
        list.addToTheLast(new Node(40));
        list.addToTheLast(new Node(50));
        list.addToTheLast(new Node(60));
        list.addToTheLast(new Node(70));
        list.addToTheLast(new Node(80));
        list.addToTheLast(new Node(90));
        System.out.println("Printing linked list :");
        list.printList(head);
        int n = list.lengthOfLinkedList();

        TreeNode bst = list.convertSortedLinkedListToBST(n);
        System.out.println("---------------");
        System.out.println("Pre order traversal of binary search tree :");
        preOrder(bst);

    }

}

When you run above program, you will get below output:

Printing linked list :
10 20 30 40 50 60 70 80 90 
---------------
Pre order traversal of binary search tree :
50 30 20 10 40 80 70 60 90

Time complexity: o(N).

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest