Problem Description

The task is to convert a Binary Search Tree (BST) into a sorted Circular Doubly-Linked List, utilizing an in-place transformation. A BST is a tree data structure where each node has at most two children, for which the left child is less than the current node, and the right child is greater. A Circular Doubly-Linked List is a series of elements in which each element points to both its previous and next element, and the list is connected end-to-end.

The conversion should maintain the following conditions:

• Each node's left pointer should reference its predecessor in the list.
• Each node's right pointer should reference its successor in the list.
• The list should be circular, with the last element pointing to the first as its successor, and the first element pointing to the last as its predecessor.

The resultant structure needs to be returned with a pointer to its smallest element, effectively the head of the list.

Flowchart Walkthrough

Let’s utilize the Flowchart to address the problem stated in Leetcode 426: "Convert Binary Search Tree to Sorted Doubly Linked List." Here’s a systematic approach according to the flowchart’s traversal:

Is it a graph?

• Not exactly. This involves a binary search tree (BST), which is a specialized form of a graph (tree structure), but the problem primarily concerns a tree.

Is it a tree?

• Yes: The main structure given and to be manipulated is a binary search tree, which is a type of tree.

Following the tree branch directly leads us to:

• DFS: Since the structure is a tree and the problem involves traversing this tree to rearrange its elements (in-order traversal), the Depth-First Search (DFS) pattern is suitable.

The DFS algorithm allows for an in-order traversal of the tree, which is ideal for accessing the nodes in a sorted manner, directly applicable for converting a BST to a sorted doubly linked list.

Conclusion: By following the flowchart, we conclude that DFS is the ideal approach for this tree-based structural manipulation problem.

Intuition

The solution to transforming a BST into a sorted doubly-linked list lies in the properties of the BST. The in-order traversal of a BST yields the nodes in ascending order, which is exactly what we want for our sorted doubly-linked list.

By performing an in-order traversal, we can visit each node in the BST in sorted order, and then adjust their left and right pointers on the fly to link them as if they were in a doubly-linked list. The following steps illustrate the approach:

1. Recursively perform an in-order traversal (left node, current node, right node) of the BST.
2. As we visit each node during the traversal, we connect it with the previously visited node (prev) to simulate the linked list's structure:
   • Make prev.right point to the current node (root), and make the current node's left point to prev. This process connects the nodes in a doubly-linked fashion.
3. For the first node, which does not have a prev, we set it as the head of our linked list.
4. After we have visited all the nodes, we connect the last visited node with the head to make the list circular.

By carefully updating the pointers as we traverse the BST, we manage to rearrange the original tree structure into a sorted circular doubly-linked list.

Learn more about Stack, Tree, Depth-First Search, Binary Search Tree, Linked List and Binary Tree patterns.

Solution Approach

The implementation of the solution follows the intuition discussed and is executed in several steps, utilizing a depth-first search (DFS) in-order traversal.

Here's a step-by-step breakdown:

1. Initialization: Before starting the DFS, we declare two variables head and prev as None. The head will eventually point to the smallest element of the BST, which will become the head of the doubly-linked list. The prev is used to keep track of the last processed node in the in-order traversal.

2. Using DFS for In-order Traversal: The function dfs is defined nested within the treeToDoublyList function. It takes a single argument root, which initially is the root of the BST.

3. Recursive Traversal: The dfs function is designed to be called recursively, going left (dfs(root.left)), processing the current node, and then going right (dfs(root.right)). This is the essence of in-order traversal.

4. Connecting Nodes: Upon visiting each node root during the traversal, we execute logic to redefine its left and right pointers:

   • If prev is not None, we set root.left to prev and prev.right to root, creating reciprocal links between prev (the predecessor) and root (the current node).
   • If prev is None, it means we are processing the very first node (smallest element) of the BST which should become the head of the doubly-linked list.

5. Update Previous Node: After linking the current node to its predecessor, we update prev to point to the current node before proceeding with the traversal to the right.

6. Closing the Circular List: Once the DFS is done processing all nodes, the prev will be pointing to the last (largest) element in the BST. At this point, we connect the prev.right to head and head.left to prev to close the loop and make the doubly-linked list circular.

In summary, the complexity of the algorithm lies in the recursive traversal of the BST and the efficient updating of the node's pointers to transform the BST structure into a doubly-linked list format.

Example Walkthrough

Let's consider a simple BST for this example:

    4
   / \
  2   5
 / \
1   3

In this BST, the traversal order for converting it into a sorted doubly-linked list using in-order traversal would be: 1 → 2 → 3 → 4 → 5.

Let's walk through the transformation process:

Initialization:

• head: initially None, will point to the node with the smallest value (in this example, it will be 1).
• prev: initially None, will keep track of the last node processed to link it with the current node.

Using DFS for In-order Traversal:

• Define and begin the recursive in-order traversal with the root (the node with the value 4).

Recursive Traversal:

• Process left subtree (2). This takes us further to the left to node 1, which is the start of the list.

• At node 1, there is no prev, so set head to 1. Since there's no previous node, we can't link it yet. prev becomes 1.

• Return to node 2 and link it with prev (which is 1). Set 1.right to 2 and 2.left to 1.

• There is no left subtree to the node 3, so we just set prev.right which is 2.right to 3 and 3.left to 2. prev is updated to 3.

• Return to 4, link 3.right to 4 and 4.left to 3. prev set to 4.

• Finally, process right subtree (5). Since there's no left child for the node with 5, we directly link 4.right to 5 and 5.left to 4. prev is updated to 5.

Closing the Circular List:

• Post traversal, prev is pointing to 5.

• Close the circular list by linking 5.right to head (which is pointing to 1) and 1.left to 5.

The result is a circular doubly-linked list with the following connections (illustrated as pointers):

1 <--> 2 <--> 3 <--> 4 <--> 5
|                             |
-------------------------------

The circular list starts at 1 and ends at 5, with 5 pointing back to 1 and 1 pointing back to 5.

Solution Implementation

Time and Space Complexity

The given Python code is designed to convert a binary search tree into a sorted, circular doubly-linked list in-place. We analyze the time complexity and space complexity of the provided code as follows:

Time Complexity:

The time complexity of the code is determined by the in-order traversal of the binary search tree.

• Each node in the tree is visited exactly once during the traversal.
• The operations performed for each node are constant time operations, including updating the previous (prev) and current node's pointers.

Therefore, if there are n nodes in the tree, the in-order traversal will take O(n) time. As a result, the overall time complexity of the code is O(n).

Space Complexity:

The space complexity of the code is determined by:

• The implicit stack space used during the recursive in-order traversal (due to dfs calls).
• No additional data structures are used that are proportional to the size of the input.

Hence, the maximum space is taken by the recursion stack, which in the worst case (a completely unbalanced tree) could have n recursive calls on the stack. However, in the best case (a completely balanced tree), the height would be log(n), and therefore the recursion stack would be O(log(n)).

In accordance with this, the space complexity of the code is:

• Worst case (skewed tree): O(n)
• Average case (balanced tree): O(log(n))

Learn more about how to find time and space complexity quickly using problem constraints.