Convert Binary Search Tree to Sorted Doubly Linked List

Medium

Google

5 views

Topics:

Linked ListsTreesRecursion

You are given the root of a binary search tree (BST). Your task is to convert this BST into a sorted circular doubly-linked list. You should modify the tree in-place, meaning you shouldn't create new nodes. The left pointer should act as the prev pointer, and the right pointer should act as the next pointer in the doubly linked list. The list must be sorted in ascending order, reflecting the BST's inherent order. The resulting linked list should also be circular, meaning the head node's prev pointer should point to the tail node, and the tail node's next pointer should point to the head node.

For example:

Example 1:

Input: [4,2,5,1,3] represented by the following tree:
```
4
```
/
2 5 / \ 1 3

Output: A circular doubly linked list representing 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 1
Example 2:

Input: [] (an empty tree)

Output: null (or an empty list)
Example 3:

Input: [1]

Output: A circular doubly linked list representing 1 <-> 1

How would you approach this problem efficiently in terms of both time and space complexity? Can you explain your solution and its Big O runtime?

Convert Binary Search Tree to Sorted Doubly Linked List

Medium

Google

5 views

Topics:

Linked ListsTreesRecursion

You are given the root of a binary search tree (BST). Your task is to convert this BST into a sorted circular doubly-linked list. You should modify the tree in-place, meaning you shouldn't create new nodes. The left pointer should act as the prev pointer, and the right pointer should act as the next pointer in the doubly linked list. The list must be sorted in ascending order, reflecting the BST's inherent order. The resulting linked list should also be circular, meaning the head node's prev pointer should point to the tail node, and the tail node's next pointer should point to the head node.

For example:

Example 1:

Input: [4,2,5,1,3] represented by the following tree:
```
4
```
/
2 5 / \ 1 3

Output: A circular doubly linked list representing 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 1
Example 2:

Input: [] (an empty tree)

Output: null (or an empty list)
Example 3:

Input: [1]

Output: A circular doubly linked list representing 1 <-> 1

How would you approach this problem efficiently in terms of both time and space complexity? Can you explain your solution and its Big O runtime?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary search tree be empty?
What should I return if the input tree is null?
Are the values in the BST guaranteed to be unique, or could there be duplicates?
Should the doubly linked list be circular, i.e., should the tail point back to the head and the head point back to the tail?
Should the `left` pointer of a node in the doubly linked list point to the previous node, and the `right` pointer point to the next node?

Brute Force Solution

Approach

The brute force method for converting a binary search tree to a sorted doubly linked list involves exploring all possible list arrangements. We can achieve this by initially extracting all the tree's values and then constructing every possible linked list from them. Finally, we can validate these lists to check if they satisfy both sorting and doubly-linked list properties.

Here's how the algorithm would work step-by-step:

First, get all the values from the tree. Think of it like emptying the tree of all its content into a big unsorted pile.
Next, try every possible order to arrange those values into a list. This means exploring all combinations, just like shuffling a deck of cards and looking at every possible sequence.
For each of these possible lists, check if it's sorted. Make sure the numbers go from smallest to largest.
Also, make sure that each item in the list is linked to the item before it and the item after it, just like a chain where each link connects to its neighbors.
If a list is both sorted and correctly linked, then we have found a solution.
We can stop as soon as we find the first valid solution. Otherwise, after checking all lists, the problem might not have a solution.

Code Implementation

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def convert_bst_to_dll_brute_force(root):
    all_values = []
    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            all_values.append(node.val)
            inorder_traversal(node.right)

    inorder_traversal(root)

    import itertools
    # Generate all possible permutations of the values.
    for permutation in itertools.permutations(all_values):
        
        is_sorted = all(permutation[i] <= permutation[i+1] for i in range(len(permutation)-1))
        
        if is_sorted:
            # Construct a doubly linked list from the sorted permutation.
            head = None
            prev = None
            
            for value in permutation:
                new_node = Node(value)
                
                if not head:
                    head = new_node
                else:
                    new_node.left = prev
                    prev.right = new_node
                    
                prev = new_node
            
            # Validate the doubly linked list.
            current = head
            while current:
                if current.left and current.left.right != current:
                    break
                if current.right and current.right.left != current:
                    break
                current = current.right
            else:
                # Found a valid sorted doubly linked list.
                return head
    
    # No valid list found.
    return None

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach first extracts all n values from the tree, which takes O(n) time. Then it generates all possible permutations of these n values. There are n! (n factorial) possible permutations. For each permutation, we check if it's sorted, which takes O(n) time, and if it's a valid doubly linked list, which also takes O(n) time. Therefore, the overall time complexity is O(n! * n) because we're iterating through each of the n! permutations and for each permutation, we perform O(n) work to check for sorted order and doubly-linked list properties. The O(n) to extract the values from the tree is insignificant in comparison.

Space Complexity

O(N!) – The algorithm initially extracts all N values from the BST, requiring O(N) space. However, the dominant space complexity arises from generating all possible permutations of these N values. Generating all permutations requires storing N! possible arrangements. Therefore the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The best way to convert a binary search tree to a sorted doubly linked list involves a clever in-place transformation during a tree traversal. We leverage the tree's structure to directly build the linked list without extra memory. The key is to traverse the tree in a special order, rearranging links as we go.

Here's how the algorithm would work step-by-step:

Start by thinking about processing the tree's nodes in a specific order, from smallest to largest, which is the order you want them in the linked list. This is called an inorder traversal.
As you visit each node during this traversal, imagine 'unhooking' its left and right connections, because those are for the tree. We are now going to use them for the linked list.
For each node you visit, connect its left 'hook' to the 'previous' node in the sorted list, and connect its right 'hook' to the 'next' node in the sorted list.
To keep track of the 'previous' node, maintain a pointer that gets updated each time you process a new node. Before processing a new node, update the previous node's right pointer to point to the current node.
The first node you visit becomes the 'head' of your linked list. Keep track of this node.
After visiting all nodes, you'll have a doubly linked list where each node points to the next smaller and larger node in the original tree. You only need to return the 'head' pointer of the new linked list.

Code Implementation

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def treeToDoublyList(self, root):
        if not root:
            return None

        self.previous_node = None
        self.head_node = None

        def inorder_traversal(node):
            if not node:
                return

            inorder_traversal(node.left)

            # Handle the first node to set the head.
            if not self.head_node:
                self.head_node = node

            # Connect the current node to the previous node.
            if self.previous_node:
                self.previous_node.right = node
                node.left = self.previous_node

            # Update the previous node to the current node.
            self.previous_node = node

            inorder_traversal(node.right)

        inorder_traversal(root)

        # Close the circle by connecting head and tail.
        self.head_node.left = self.previous_node
        self.previous_node.right = self.head_node

        return self.head_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs an inorder traversal of the binary search tree, visiting each node exactly once. During the traversal, a constant amount of work is performed at each node to rearrange the pointers for the doubly linked list. Since the number of nodes visited is equal to n (the number of nodes in the tree), and the work done per node is constant, the total time complexity is proportional to n, resulting in O(n).

Space Complexity

O(H) – The space complexity is determined by the recursion depth during the inorder traversal. In the worst case, the tree is skewed, resembling a linked list, leading to a recursion depth of N, where N is the number of nodes in the tree. In the best and average cases, the tree is balanced, resulting in a recursion depth of H, where H is the height of the tree. Therefore, the auxiliary space required for the call stack is O(H), where H is the height of the BST.

Edge Cases

Case	How to Handle
Null or empty BST	Return null immediately as there's nothing to convert.
BST with only one node	Create a doubly linked list with the single node pointing to itself bidirectionally.
BST with all identical values	In-order traversal will correctly order the duplicate values in the doubly linked list.
Highly skewed BST (left or right leaning)	In-order traversal remains correct but might affect performance due to recursion depth for extremely unbalanced trees.
BST with negative, zero, and positive values	The in-order traversal naturally handles different value ranges, correctly sorting the list.
Large BST potentially exceeding stack space (recursion depth)	Consider converting the recursive in-order traversal to an iterative approach using a stack to avoid stack overflow.
Integer overflow when calculating node values (if applicable based on problem constraints)	Ensure the data type used to store node values is large enough or handle potential overflows explicitly.
Memory constraints with an extremely large BST	If memory is a significant constraint, investigate in-place conversion strategies if possible, or consider a disk-based approach for extremely large BSTs.