We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convert Binary Search Tree to Sorted Doubly Linked List

Number: 758

Difficulty: Medium

Paid? Yes

Companies: Meta, TikTok, Microsoft, Nvidia

Problem Description

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place. The left pointer of each node represents the predecessor and the right pointer represents the successor. The resulting list should be circular, meaning the predecessor of the smallest element is the largest element and the successor of the largest element is the smallest.

Key Insights

  • Use an in-order traversal to process nodes in sorted order.
  • Maintain pointers to connect the current node with the previously visited node.
  • After traversal, connect the head and tail of the list to make it circular.
  • The in-place constraint means no new nodes (or extra data structures for node storage) are created.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited once during the in-order traversal. Space Complexity: O(n) – Due to the recursion stack in the case of an unbalanced tree. For a balanced tree, it can be O(log n).

Solution

We solve the problem using an in-order depth-first search (DFS) traversal to ensure nodes are accessed in sorted order. While traversing:

  1. Use a helper recursive function to perform the in-order traversal.
  2. Maintain a reference to the previously processed node (prev) and to the head of the list.
  3. For each node, connect it with the previous node by setting prev.right to the current node and current node.left to prev.
  4. Once traversal is complete, connect the head and tail (last node) to make the list circular. The algorithm uses recursion, and the key trick is to update the pointers while unwinding the recursion.

Code Solutions

# Definition for a Node.
# class Node:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left  # Pointer to predecessor in DLL
#         self.right = right  # Pointer to successor in DLL

def treeToDoublyList(root):
    # If the BST is empty, return None
    if not root:
        return None

    # Initialize the pointers for the previous node and head node of the doubly linked list
    prev = None
    head = None

    # Helper function to perform in-order traversal
    def inorder(node):
        nonlocal prev, head
        if not node:
            return

        # Traverse left subtree
        inorder(node.left)

        # Process current node: if prev is None, it means this is the smallest element
        if prev is None:
            head = node
        else:
            # Connect the previous node (predecessor) with the current node (successor)
            prev.right = node
            node.left = prev

        # Update prev to current node for the next iteration
        prev = node

        # Traverse right subtree
        inorder(node.right)

    # Start in-order traversal starting from the root
    inorder(root)

    # After traversal, prev points to the last node. Connect head and tail to make DLL circular.
    head.left = prev
    prev.right = head

    # Return the head node of the circular doubly linked list.
    return head
← Back to All Questions