LeetCode //C - 109. Convert Sorted List to Binary Search Tree

109. Convert Sorted List to Binary Search Tree

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

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\ast 10^4]$.
• $-10^5<=Node.val<=10^5$

From: LeetCode
Link: 109. Convert Sorted List to Binary Search Tree

---

Solution:

Ideas:

1. Find the Middle Element: The middle element of the sorted linked list will be the root of the BST. The left half of the list will form the left subtree, and the right half will form the right subtree.
2. Recursive Approach: Use recursion to build the tree. For each recursive call, find the middle of the current segment of the linked list, create a tree node, and recursively build the left and right subtrees.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* createTreeNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Helper function to find the middle element of the linked list.
struct ListNode* findMiddleElement(struct ListNode* head) {
    struct ListNode* prevPtr = NULL;
    struct ListNode* slowPtr = head;
    struct ListNode* fastPtr = head;
    
    // Move fastPtr by 2 and slowPtr by 1
    while (fastPtr != NULL && fastPtr->next != NULL) {
        prevPtr = slowPtr;
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
    }
    
    // Handling the case when slowPtr might be the head
    if (prevPtr != NULL) {
        prevPtr->next = NULL;
    }
    
    return slowPtr;
}

struct TreeNode* sortedListToBST(struct ListNode* head) {
    // Base case
    if (head == NULL) {
        return NULL;
    }
    
    // Find the middle element of the linked list
    struct ListNode* mid = findMiddleElement(head);
    
    // The middle element becomes the root
    struct TreeNode* node = createTreeNode(mid->val);
    
    // Base case when there is just one element in the linked list
    if (head == mid) {
        return node;
    }
    
    // Recursively construct the left subtree and right subtree
    node->left = sortedListToBST(head);
    node->right = sortedListToBST(mid->next);
    
    return node;
}

// Function to print the tree in order for testing
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77