Convert sorted Linked List to balanced BST

ghz 10months ago ⋅ 215 views

To convert a sorted linked list to a balanced binary search tree (BST), you can follow a recursive approach where you divide the linked list into two halves and recursively build the left and right subtrees of the BST. Here's the Java implementation:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public class SortedListToBST {
    private ListNode current;

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;

        int size = getSize(head);
        current = head;

        return sortedListToBSTHelper(size);
    }

    private TreeNode sortedListToBSTHelper(int size) {
        if (size <= 0)
            return null;

        TreeNode left = sortedListToBSTHelper(size / 2);
        TreeNode root = new TreeNode(current.val);
        current = current.next;
        TreeNode right = sortedListToBSTHelper(size - size / 2 - 1);

        root.left = left;
        root.right = right;

        return root;
    }

    private int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }

    // Utility function to print the inorder traversal of a binary tree
    private void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    }

    public static void main(String[] args) {
        // Example usage
        ListNode head = new ListNode(-10);
        head.next = new ListNode(-3);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(9);

        SortedListToBST solution = new SortedListToBST();
        TreeNode root = solution.sortedListToBST(head);
        
        System.out.println("Inorder traversal of constructed BST:");
        solution.inorderTraversal(root);
    }
}

In this implementation:

  • sortedListToBST is the main method that kicks off the conversion process. It calculates the size of the linked list and initializes the current pointer to the head of the list. It then calls a helper method, sortedListToBSTHelper, passing the size of the list.
  • sortedListToBSTHelper recursively constructs the balanced BST by dividing the list into two halves. It constructs the left subtree first, then constructs the root node, and finally constructs the right subtree.
  • getSize calculates the size of the linked list.
  • inorderTraversal is a utility function to print the inorder traversal of the constructed BST.

You can run the main method with your own example linked list to see the conversion in action.

#algorithm