Convert Sorted List to Binary Search Tree Leetcode Solution

In this post, we are going to solve the Convert Sorted List to Binary Search Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of Contents

Problem

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Constraints:

The number of nodes in head is in the range [0, 2 * 10⁴].
-10⁵ <= Node.val <= 10⁵

Now, let’s see the leetcode solution of Convert Sorted List to Binary Search Tree Leetcode Solution.

Convert Sorted List to Binary Search Tree Leetcode Solution in Python

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

Convert Sorted List to Binary Search Tree Leetcode Solution in CPP

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;
  }
};

Convert Sorted List to Binary Search Tree Leetcode Solution in Java

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;
  }
}

Note: This problem Convert Sorted List to Binary Search Tree is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.