109 || Convert Sorted List to Binary Search Tree || Leetcode Daily Problem

Problem Link :- leetcode-109

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.

Significance of problem

The significance of the problem lies in its bridging of two fundamental data structures—linked lists and binary search trees (BST). Converting a sorted linked list to a height-balanced BST not only showcases the synergy between these structures but also offers insights into algorithmic design and recursive problem-solving.

The problem encourages a deep exploration of recursion as a powerful tool for constructing balanced binary search trees. The code elegantly divides the problem into sub-problems by identifying the middle element of the linked list, creating a recursive approach that efficiently constructs a balanced BST.

Moreover, this problem addresses real-world scenarios where data organization impacts computational efficiency. Understanding how a sorted linked list can be transformed into a balanced binary search tree is crucial for optimizing search and retrieval operations, particularly in applications where maintaining a balance in data distribution is paramount.

Additionally, the problem promotes a holistic understanding of data structure transformations, emphasizing the adaptability required to manipulate data representations effectively. Mastering this problem enhances algorithmic proficiency and lays the groundwork for tackling more complex challenges involving the manipulation and transformation of different data structures.

Easiest Explanation

Do you know what a linked list is? It's a way to store a bunch of things, like toys or books, in a line, where each thing is connected to the next thing.

Now, imagine you have a linked list of numbers that are in order from smallest to largest, like this: 1 -> 2 -> 3 -> 4 -> 5. Do you see how they are in order?

Well, a binary search tree is like a special kind of linked list where the numbers are organized in a way that makes it easy to search for a particular number. The tree is made up of nodes, where each node has a number and two branches. The branches lead to other nodes that have smaller or larger numbers.

So, the problem is to take the linked list of numbers that are already sorted and turn it into a balanced binary search tree. This means that we want to arrange the numbers in the tree so that it's not too lopsided, with lots of branches on one side and few on the other.

To do this, we'll take the middle number of the linked list and make it the root of our tree. Then, we'll take the numbers on the left side of the middle number and make a subtree out of them, and we'll do the same thing with the numbers on the right side. We'll keep doing this recursively until we have a balanced binary search tree with all the numbers from the linked list

I hope that explanation helps! If you find any difficulty in solving, feel free to comment with your doubts.

Python Code :

class Solution:
        def solve(self, head, tail):
            if head == tail:
                return None

            if head.next == tail:
                root = TreeNode(head.val)
                return root

            mid = head
            temp = head

            while temp != tail and temp.next != tail:
                mid = mid.next
                temp = temp.next.next

            root = TreeNode(mid.val)
            root.left = self.solve(head, mid)
            root.right = self.solve(mid.next, tail)

            return root

        def sortedListToBST(self, head):
            return self.solve(head, None)

CPP Code

class Solution {
public:
    TreeNode* solve(ListNode* head, ListNode* tail)
    {
        if(head==tail) return NULL;

        if(head->next == tail){
            TreeNode* root = new TreeNode(head->val);
            return root;
        }
        
        ListNode* mid = head,*temp = head;

        while(temp != tail && temp->next != tail){
            mid = mid->next;
            temp = temp->next->next;
        }
        TreeNode* root = new TreeNode(mid->val);
        root->left = solve(head,mid);
        root->right = solve(mid->next,tail);

        return root;

    }
    TreeNode* sortedListToBST(ListNode* head) 
    {
        return solve(head,NULL);    
    }
};
    

Here's how the function works:

The solve function takes two parameters: head, which is the pointer to the first node of the linked list, and tail, which is the pointer to the last node of the linked list. It returns a pointer to the root node of the binary search tree.

The if(head==tail) check is the base case, where there are no more nodes left in the linked list. In this case, the function returns NULL to indicate that there are no more nodes to add to the binary search tree.

The if(head->next == tail) check is another base case, where there is only one node left in the linked list. In this case, a new TreeNode object is created with the value of the remaining node, and that node is returned as the root node of the binary search tree.

The while loop finds the middle node of the linked list. The mid pointer starts at the head node, and the temp pointer starts at the head node as well. On each iteration of the loop, the mid pointer moves one node forward, while the temp pointer moves two nodes forward. When the temp pointer reaches the tail node, or the node before the tail node, the mid pointer will be pointing to the middle node of the linked list.

The middle node is then used to create a new TreeNode object, which becomes the root node of the binary search tree. The left pointer of the root node is set to the result of calling the solve function recursively with the head node and the mid node as the parameters. The right pointer of the root node is set to the result of calling the solve function recursively with the mid->next node and the tail node as the parameters.

The sortedListToBST function is the main function that is called to convert the linked list to a binary search tree. It simply calls the solve function with the head node and NULL as the parameters and returns the result.

Learning Outcomes

Solving the sorted linked list to height-balanced BST problem yields rich learning outcomes across various aspects of computer science. Firstly, the problem enhances proficiency in recursive algorithmic design. The recursive solution elegantly breaks down the task into smaller sub-problems, showcasing the power and elegance of recursive thinking—a skill applicable in a myriad of computational challenges.

The problem fosters a deep understanding of the relationship between linked lists and binary search trees. Developers gain insights into how data structures can be transformed to meet specific requirements, laying the groundwork for comprehending and manipulating diverse data representations.

Furthermore, the problem reinforces the importance of balance in binary search trees for efficient search and retrieval operations. Learners grasp the practical implications of maintaining balanced structures, a concept crucial in optimizing algorithms for real-world applications, such as databases and information retrieval systems.

Additionally, the problem cultivates adaptability in handling different data structures. The transformation from a linked list to a binary search tree underscores the versatility required for efficient data manipulation, providing learners with skills applicable across various domains in computer science.

Conclusion

In conclusion, converting a sorted linked list to a height-balanced binary search tree not only sharpens recursive algorithmic skills but also underscores the transformative potential of data structure manipulation. This problem provides a gateway for learners to comprehend the synergy between linked lists and binary search trees, fostering a nuanced understanding of balanced structures for efficient search operations.

Mastering this task equips developers with essential skills in recursive problem-solving, data structure transformations, and the practical implications of maintaining balance in binary search trees—skills fundamental for navigating diverse computational challenges.

Stay up-to-date with our latest content by subscribing to our channel! Don't miss out on our next video - make sure to subscribe today.