Similar Problems

Similar Problems not available

Convert Sorted List To Binary Search Tree - Leetcode Solution

Companies:

LeetCode:  Convert Sorted List To Binary Search Tree Leetcode Solution

Difficulty: Medium

Topics: binary-search-tree linked-list binary-tree tree  

Problem statement: Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution: To solve this problem, we can follow the below approach:

  1. First, we need to find the middle element of the linked list.
  2. Then we can create a TreeNode with the middle element.
  3. We can then recursively create the left and right subtrees using the nodes before and after the middle element in the linked list.
  4. We can repeat the above steps until the entire list is used up or we have no more nodes to create subtrees.

Below is the code implementation in Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        
        # find middle node using slow and fast pointer
        slow, fast = head, head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # create a TreeNode with the middle value
        root = TreeNode(slow.next.val)
        
        # recursively create left and right subtrees
        rightHead = slow.next.next
        slow.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(rightHead)
        
        return root

The time complexity of the above code is O(n log n), where n is the number of nodes in the linked list. This is because we need to find the middle element using the slow and fast pointer, which takes O(n) time. And then for each subtree, we need to recursively process half the number of nodes, which also takes O(n) time. Hence the overall time complexity is O(n log n).

The space complexity of the above code is O(log n), which is the space required for the recursion stack. This is because for each level of the recursion tree, we only need to store the root of the subtree.

Test Cases: Let's consider a few test cases to validate our solution:

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 following BST: 0 /
-3 9 / / -10 5

Example 2: Input: head = [1,3] Output: [3,1] Explanation: One possible answer is [3,1], which represents the following BST: 3
1

Example 3: Input: head = [] Output: []

In conclusion, we have successfully solved the Convert Sorted List to Binary Search Tree problem on Leetcode using a recursive approach.

Convert Sorted List To Binary Search Tree Solution Code

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11/**
12 * Definition for a binary tree node.
13 * struct TreeNode {
14 *     int val;
15 *     TreeNode *left;
16 *     TreeNode *right;
17 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
18 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
19 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
20 * };
21 */
22class Solution {
23public:
24    TreeNode* sortedListToBST(ListNode* head) {
25        
26        // Base case
27        if(head == NULL){
28            return NULL;
29        }
30        
31        // Find the middle element for the list
32        ListNode *mid = findMiddle(head);
33        
34        // Make the middle element the root of the tree
35        TreeNode *root = new TreeNode(mid->val);
36        
37        // Base case when there is only one element in the linked list
38        if(head == mid){
39            return root;
40        }
41        
42        // Recursively form balanced BSTs using the left and right halves of the original list.
43        root->left = sortedListToBST(head);
44        root->right = sortedListToBST(mid->next);
45        
46        return root;
47    }
48    
49    ListNode* findMiddle(ListNode *head){
50        
51        // The pointer used to disconnect the left half of the linked list from the mid node.
52        ListNode *prevPtr = NULL;
53        // Slow pointer used to form the left half of the linked list.
54        ListNode *slowPtr = head;
55        // Fast pointer used to form the right half of the linked list.
56        ListNode *fastPtr = head;
57        
58        // Iterate until fastPr doesn't reach the end of the linked list.
59        while(fastPtr != NULL && fastPtr->next != NULL){
60            fastPtr = fastPtr->next->next;
61            prevPtr = slowPtr;
62            slowPtr = slowPtr->next;
63        }
64        
65        // Handling the case when slowPtr was equal to head.
66        if(prevPtr != NULL){
67            prevPtr->next = NULL;
68        }
69        
70        return slowPtr;
71    }
72};