109. Convert Sorted List to Binary Search Tree

Approach 1: Recursion

• Time: $O(n\log n)$
• Space: $O(\log n)$

C++JavaPython

class Solution {
 public:
  TreeNode* sortedListToBST(ListNode* head) {
    if (head == nullptr)
      return nullptr;
    if (!head->next)
      return new TreeNode(head->val);

    ListNode* mid = findMid(head);
    TreeNode* root = new TreeNode(mid->val);
    root->left = sortedListToBST(head);
    root->right = sortedListToBST(mid->next);

    return root;
  }

 private:
  ListNode* findMid(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
      prev = slow;
      slow = slow->next;
      fast = fast->next->next;
    }
    prev->next = nullptr;

    return slow;
  }
};

class Solution {
  public TreeNode sortedListToBST(ListNode head) {
    if (head == null)
      return null;
    if (head.next == null)
      return new TreeNode(head.val);

    ListNode mid = findMid(head);
    TreeNode root = new TreeNode(mid.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(mid.next);

    return root;
  }

  private ListNode findMid(ListNode head) {
    ListNode prev = null;
    ListNode slow = head;
    ListNode fast = head;

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

    return slow;
  }
}

class Solution:
  def sortedListToBST(self, head: ListNode) -> TreeNode:
    def findMid(head: ListNode) -> ListNode:
      prev = None
      slow = head
      fast = head

      while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
      prev.next = None

      return slow

    if not head:
      return None
    if not head.next:
      return TreeNode(head.val)

    mid = findMid(head)
    root = TreeNode(mid.val)
    root.left = self.sortedListToBST(head)
    root.right = self.sortedListToBST(mid.next)

    return root

Approach 2: Recursion + Array

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  TreeNode* sortedListToBST(ListNode* head) {
    vector<int> A;

    // Construct the array
    for (ListNode* curr = head; curr; curr = curr->next)
      A.push_back(curr->val);

    return helper(A, 0, A.size() - 1);
  }

 private:
  TreeNode* helper(const vector<int>& A, int l, int r) {
    if (l > r)
      return nullptr;

    const int m = (l + r) / 2;
    TreeNode* root = new TreeNode(A[m]);
    root->left = helper(A, l, m - 1);
    root->right = helper(A, m + 1, r);
    return root;
  }
};

class Solution {
  public TreeNode sortedListToBST(ListNode head) {
    List<Integer> A = new ArrayList<>();

    // Construct the array
    for (ListNode curr = head; curr != null; curr = curr.next)
      A.add(curr.val);

    return helper(A, 0, A.size() - 1);
  }

  private TreeNode helper(List<Integer> A, int l, int r) {
    if (l > r)
      return null;

    final int m = (l + r) / 2;
    TreeNode root = new TreeNode(A.get(m));
    root.left = helper(A, l, m - 1);
    root.right = helper(A, m + 1, r);
    return root;
  }
}

class Solution:
  def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
    A = []

    # Construct the array
    curr = head
    while curr:
      A.append(curr.val)
      curr = curr.next

    def helper(l: int, r: int) -> Optional[TreeNode]:
      if l > r:
        return None

      m = (l + r) // 2
      root = TreeNode(A[m])
      root.left = helper(l, m - 1)
      root.right = helper(m + 1, r)
      return root

    return helper(0, len(A) - 1)

Approach 3: Inorder Simulation

• Time: $O(n)$
• Space: $O(\log n)$

C++JavaPython

class Solution {
 public:
  TreeNode* sortedListToBST(ListNode* head) {
    this->head = head;
    return helper(0, getLength(head) - 1);
  }

 private:
  ListNode* head;

  TreeNode* helper(int l, int r) {
    if (l > r)
      return nullptr;

    const int m = (l + r) / 2;

    // Simulate inorder traversal: recursively form the left half
    TreeNode* left = helper(l, m - 1);

    // Once left half is traversed, process the current node
    TreeNode* root = new TreeNode(head->val);
    root->left = left;

    // Maintain the invariance
    head = head->next;

    // Simulate inorder traversal: recursively form the right half
    root->right = helper(m + 1, r);
    return root;
  }

  int getLength(ListNode* head) {
    int length = 0;
    for (ListNode* curr = head; curr; curr = curr->next)
      ++length;
    return length;
  }
};

class Solution {
  public TreeNode sortedListToBST(ListNode head) {
    this.head = head;
    return helper(0, getLength(head) - 1);
  }

  private ListNode head;

  private TreeNode helper(int l, int r) {
    if (l > r)
      return null;

    final int m = (l + r) / 2;

    // Simulate inorder traversal: recursively form the left half
    TreeNode left = helper(l, m - 1);

    // Once left half is traversed, process the current node
    TreeNode root = new TreeNode(head.val);
    root.left = left;

    // Maintain the invariance
    head = head.next;

    // Simulate inorder traversal: recursively form the right half
    root.right = helper(m + 1, r);

    return root;
  }

  private int getLength(ListNode head) {
    int length = 0;
    for (ListNode curr = head; curr != null; curr = curr.next)
      ++length;
    return length;
  }
}

class Solution:
  def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
    def helper(l: int, r: int) -> Optional[TreeNode]:
      nonlocal head
      if l > r:
        return None

      m = (l + r) // 2

      # Simulate inorder traversal: recursively form the left half
      left = helper(l, m - 1)

      # Once left half is traversed, process the current node
      root = TreeNode(head.val)
      root.left = left

      # Maintain the invariance
      head = head.next

      # Simulate inorder traversal: recursively form the right half
      root.right = helper(m + 1, r)
      return root

    return helper(0, self._getLength(head) - 1)

  def _getLength(self, head: Optional[ListNode]) -> int:
    length = 0
    curr = head
    while curr:
      length += 1
      curr = curr.next
    return length