Convert Binary Search Tree to Sorted Doubly Linked List

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.

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.