Convert Sorted List to Binary Search Tree LeetCode Solution

Here, We see Convert Sorted List to Binary Search Tree problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

Convert Sorted List to Binary Search Tree LeetCode Solution

Convert Sorted List to Binary Search Tree LeetCode Solution

Problem Statement ->

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

Convert Sorted List to Binary Search Tree LeetCode Solution
fig-1
Example 1: (fig-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: []

Convert Sorted List to Binary Search Tree Leetcode Solution C++ ->

class Solution { public: TreeNode* sortedListToBST(ListNode* head) { if(!head) return NULL; if(!head->next) return new TreeNode(head->val); auto slow = head; auto fast = head; auto pre = head; while(fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = 0; // break two halves TreeNode* root = new TreeNode(slow->val); root->left = sortedListToBST(head); root->right = sortedListToBST(slow->next); return root; } };
Code language: C++ (cpp)

Convert Sorted List to Binary Search Tree Leetcode Solution Java ->

class Solution { public TreeNode sortedListToBST(ListNode head) { if(head==null) return null; return toBST(head,null); } public TreeNode toBST(ListNode head, ListNode tail){ ListNode slow = head; ListNode fast = head; if(head==tail) return null; while(fast!=tail&&fast.next!=tail){ fast = fast.next.next; slow = slow.next; } TreeNode thead = new TreeNode(slow.val); thead.left = toBST(head,slow); thead.right = toBST(slow.next,tail); return thead; } }
Code language: Java (java)

Convert Sorted List to Binary Search Tree Leetcode Solution JavaScript ->

var sortedListToBST = function(head) { let curr = head, count = 0 while (curr) curr = curr.next, count++ const treeify = (i, j) => { if (j < i) return null let mid = i + j >> 1, node = new TreeNode() node.left = treeify(i, mid - 1) node.val = curr.val, curr = curr.next node.right = treeify(mid + 1, j) return node } curr = head return treeify(1, count) };
Code language: JavaScript (javascript)

Convert Sorted List to Binary Search Tree Leetcode Solution Python ->

class Solution(object): def sortedListToBST(self, head): if not head: return if not head.next: return TreeNode(head.val) slow, fast = head, head.next.next while fast and fast.next: fast = fast.next.next slow = slow.next tmp = slow.next slow.next = None root = TreeNode(tmp.val) root.left = self.sortedListToBST(head) root.right = self.sortedListToBST(tmp.next) return root
Code language: Python (python)