Vultr DocsLatest Content

Convert Binary Search Tree to Sorted Doubly Linked List

Updated on 08 May, 2025
Convert Binary Search Tree to Sorted Doubly Linked List header image

Problem Statement

In this task, we are required to convert a Binary Search Tree (BST) into a sorted Circular Doubly-Linked List. The conversion should be done in place, meaning that the original data structure is modified directly without using extra space for another data structure. In the context of doubly-linked lists, each node has two pointers: left (pointing to the predecessor) and right (pointing to the successor). For a circular doubly linked list specifically, these connections are cyclical: the left pointer of the first element (smallest value) must point to the last element, and the right pointer of the last element (largest value) must point back to the first element. The ultimate goal of this transformation is to return the pointer to the smallest element of the resulting circular doubly-linked list.

Examples

Example 1

Input:

root = [4,2,5,1,3]

Output:

[1,2,3,4,5]

Explanation:

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2

Input:

root = [2,1,3]

Output:

[1,2,3]

Constraints

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
  • All the values of the tree are unique.

Approach and Intuition

  1. Understanding the Connection Between BST and Doubly Linked List

    • A BST inherently stores elements in a sorted order via its tree structure. This property makes it suitable for transformation into a sorted doubly linked list, where traversal from a node to its in-order successor or predecessor is straightforward.

  2. Using In-Order Traversal

    • In-Order traversal of a BST visits nodes in a non-decreasing order. This sequence of visiting can be utilized to rearrange the pointers (left for predecessor and right for successor) to convert the structure to a doubly linked list.

  3. Performing the In-Place Conversion

    • As nodes are visited in in-order:
      • Connect each node's left pointer to the previously visited node.
      • Connect the previous node's right pointer to the current node.
    • This gradually links all nodes in a doubly linked manner.

  4. Finalizing the Circular Connectivity

    • Post traversal, the first visited node (smallest, having no predecessor in BST context) and the last visited node (largest, having no successor in BST context) are connected to each other to make the list circular.

  5. Returning the Head of the List

    • The first node visited during the in-order traversal is the smallest element and hence serves as the head of the doubly linked list.

Using the provided examples as a reference:

  • For BST [4,2,5,1,3], converting this into the circular doubly linked format involves rearranging connections starting from the node with value 1 and proceeding with 2,3,4,5, then linking 5 back to 1.
  • Similar logic is applied for the smaller tree [2,1,3], producing a linked list starting from 1 and moving through 2 to 3, and back to 1.

The constraints ensuring unique values and the manageable size of the BST (up to 2000 nodes) ensure that the in-order traversal and linkage restructuring can be managed efficiently. This task highlights the importance of understanding properties of BSTs and linked lists, and how in-place modifications using pointer manipulations can achieve complex transformations.

Solutions

  • C++
  • Java
cpp 
class Solution {
  public:
  Node* head = NULL;
  Node* tail = NULL;

  void traverse(Node* current) {
    if (current) {
      traverse(current->left);

      if (tail) {
        tail->right = current;
        current->left = tail;
      } else {
        head = current;
      }
      tail = current;

      traverse(current->right);
    }
  }

  Node* convertToDoubleList(Node* root) {
    if (!root) return NULL;

    traverse(root);

    tail->right = head;
    head->left = tail;
    return head;
  }
};

The given C++ code provides a method for transforming a Binary Search Tree (BST) into a sorted doubly linked list. It utilizes an in-order traversal to achieve this, ensuring that the elements maintain their sorted order as per BST properties. Here's a breakdown of how the code functions:

  • Class Solution - This class includes the transformation logic.
  • Node Pointers - Two pointers, head and tail, are used to keep track of the double linked list's beginning and end.
  • traverse Method - This is a helper function that performs an in-order traversal on the BST. During traversal:
    • When moving left, it first processes all left children recursively.
    • It then sets the current node in place in the linked list. If tail (the last element processed) is not null, it links the tail to the current node and vice versa. If tail is null, it means the current node is the head of the list.
    • The tail is updated to the current node before moving to the right.
    • It processes all right children recursively after updating links.
  • convertToDoubleList Function - This function prepares the conversion:
    • It checks if the root is null, returning NULL if true, handling the edge case of an empty tree.
    • Calls traverse with the root node to fill out the linked list.
    • It links the tail to head and vice versa to circularize the doubly linked list, making the last node point back to the first node and the first node back to the last.
    • Returns the head of the newly formed doubly linked list, providing the entry point to the list.

This function ensures that all nodes from the BST are included in the doubly linked list in the original sorted order, with each node having pointers to both its previous and next nodes, forming a circular doubly linked list. The usage of in-order traversal is key to achieving the sorted order in the list.

java 
class Solution {
  Node head = null;
  Node tail = null;

  public void traverse(Node node) {
    if (node != null) {
      traverse(node.left);
      
      if (tail != null) {
        tail.right = node;
        node.left = tail;
      } else {
        head = node;
      }
      tail = node;

      traverse(node.right);
    }
  }

  public Node treeToDoublyList(Node root) {
    if (root == null) return null;

    traverse(root);

    tail.right = head;
    head.left = tail;
    return head;
  }
}

In the provided Java solution, you'll convert a Binary Search Tree (BST) into a sorted doubly linked list. Follow these detailed steps to understand the implemented approach:

  • Define two class-level variables head and tail to keep track of the start and end of the doubly linked list.
  • Implement a helper method traverse(Node node) which uses in-order traversal to access the elements of the BST in sorted order:
    • If the current node isn't null, proceed with the traversal for the left child.
    • Handle the conversion:
      • If tail isn't null, link the current tail's right to the node and the node's left to the tail.
      • If tail is null, initialize the head to this node since it's the smallest element.
      • Update tail to the current node.
    • Continue the traversal for the right child.
  • The treeToDoublyList(Node root) method initializes the process:
    • If the input root is null, return null as there's nothing to convert.
    • Use the traverse method to transform the BST into a doubly linked list.
    • Connect the tail of the list to the head and the head's left to the tail to make the list circular.
    • Return the head as the entry point to the sorted doubly linked list.

By following these steps, the algorithm effectively modifies the structure of the BST into a circular doubly linked list, maintaining the sorted order of the data. This solution ensures each node is visited once, preserving the initial properties of the BST while transforming it into a different data structure.

Comments

No comments yet.