RBST: Convert a Sorted Linked List to a Height-Balanced BST

📌 Problem Requirements

• Convert a sorted singly linked list into a height-balanced binary search tree (BST).
• A height-balanced BST is a binary tree in which the depth of the two subtrees of any node never differs by more than one.

📌 Constraints & Conditions

1. Binary Search Tree (BST) Property:
   • For each node, all values in the left subtree must be less than the node’s value.
   • All values in the right subtree must be greater than the node’s value.
2. Height-Balanced Condition:
   • The left and right subtrees' heights must differ by at most one.
3. Optimal Construction Strategy:
   • Find the middle element of the linked list and use it as the root node.
   • Recursively apply this process for the left and right halves of the list to build the BST.
4. Time Complexity Requirement:
   • The solution should run in O(N) time complexity, where N is the number of nodes in the linked list.
   • The algorithm must achieve O(log N) height for the constructed BST.
5. Linked List Constraints:
   • The given linked list is sorted in ascending order.
   • It contains no duplicate values.

class TreeNode {

  int val;
  TreeNode left, right;

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


class ListNode {

  int val;
  ListNode next;

  ListNode(int val) {
    this.val = val;
  }
}

 

public class Main {

  public static void main(String[] args) {
    // Create a sorted linked list (Example: [-10, -3, 0, 5, 9])
    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);

    // Perform conversion
    SortedListToBST converter = new SortedListToBST();
    TreeNode root = converter.sortedListToBST(head);

    // Print BST (Inorder Traversal)
    System.out.println("BST (Inorder Traversal):");
    inorderTraversal(root);
  }

  // Inorder Traversal (Left - Root - Right)
  private static void inorderTraversal(TreeNode root) {
    if (root == null) {
      return;
    }
    inorderTraversal(root.left);
    System.out.print(root.val + " ");
    inorderTraversal(root.right);
  }
}

 

---

1. first approach

 

2. second approach

 

 

 

public class SortedListToBST {

  public TreeNode sortedListToBST(ListNode node) {
    if (node == null) return null;
    return buildTreeNode(node, null);
  }

  private TreeNode buildTreeNode(ListNode start, ListNode end) {
  //The start node and the end node become the same
  //There are no child nodes.
    if (start == end) {
      return null;
    }
    ListNode middle = findMiddle(start, end);
    TreeNode root = new TreeNode(middle.val);
    root.left = buildTreeNode(start, middle);
    // Since `middle` has already been used to construct the left subtree,
    // `middle.next` is needed when constructing the right subtree.
    root.right = buildTreeNode(middle.next, end);
    return root;
  }

  // Find the middle node
  private static ListNode findMiddle(ListNode start, ListNode end) {
    ListNode slow = start;
    ListNode fast = start;

    while (fast != end && fast.next != end) {
      slow = slow.next;
      fast = fast.next.next;
    }

    return slow;
  }
}

 

Tryyyyyyyyyyyyyyyyyyyyyyyy

1. Find the termination condition.
2. Set the return value.