426. Convert Binary Search Tree to Sorted Doubly Linked List

MediumStackTreeDepth-First SearchBinary Search TreeLinked ListBinary TreeDoubly-Linked List
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's consider a simple BST for this example:

1    4
2   / \
3  2   5
4 / \
51   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):

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

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

Solution Implementation

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8class Solution:
9    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
10        # Helper function to perform the in-order traversal of the tree.
11        def in_order_traverse(node):
12            # Base case: if the node is None, return to the previous call.
13            if node is None:
14                return
15          
16            # Recursive case: traverse the left subtree.
17            in_order_traverse(node.left)
18          
19            # Process the current node.
20            nonlocal previous, head
21            if previous:
22                # Link the previous node with the current node from the left.
23                previous.right = node
24                # Link the current node with the previous node from the right.
25                node.left = previous
26            else:
27                # If this node is the leftmost node, it will be the head of the doubly linked list.
28                head = node
29            # Mark the current node as the previous one before the next call.
30            previous = node
31          
32            # Recursive case: traverse the right subtree.
33            in_order_traverse(node.right)
34
35        # If the input tree is empty, return None.
36        if root is None:
37            return None
38
39        # Initialize the head and previous pointer used during the in-order traversal.
40        head = previous = None
41        # Perform the in-order traversal to transform the tree to a doubly linked list.
42        in_order_traverse(root)
43        # Connect the last node visited (previous) with the head of the list to make it circular.
44        previous.right = head
45        head.left = previous
46
47        # Return the head of the doubly linked list.
48        return head
49
1class Solution {
2
3    // This 'previous' node will help in keeping track of the previously processed node in the inorder traversal
4    private Node previous;
5
6    // The 'head' node will serve as the head of the doubly linked list
7    private Node head;
8
9    // Convert a binary search tree to a sorted, circular, doubly-linked list
10    public Node treeToDoublyList(Node root) {
11        if (root == null) {
12            return null; // If the tree is empty, there is nothing to process or convert
13        }
14
15        // Initialize 'previous' and 'head' as null before the depth-first search
16        previous = null;
17        head = null;
18
19        // Start the inorder traversal from the root to convert the BST into a sorted list
20        inorderTraversal(root);
21
22        // After the traversal, connect the last node with the 'head' to make it circular
23        previous.right = head;
24        head.left = previous;
25
26        return head; // Return the head of the doubly linked list
27    }
28
29    // Inorder traversal of the binary search tree
30    private void inorderTraversal(Node node) {
31        if (node == null) {
32            return; // Base case for the recursive function, stop if the current node is null
33        }
34
35        // Recursively process the left subtree
36        inorderTraversal(node.left);
37
38        // In the inorder traversal, 'previous' will be null only for the leftmost node
39        if (previous != null) {
40            // Connect the previous node's right to the current node
41            previous.right = node;
42          
43            // Connect the current node's left to the previous node
44            node.left = previous;
45        } else {
46            // If 'previous' is null, it means we are at the leftmost node which is the 'head' of the list
47            head = node;
48        }
49
50        // Update 'previous' to be the current node before moving to the right subtree
51        previous = node;
52
53        // Recursively process the right subtree
54        inorderTraversal(node.right);
55    }
56}
57
1class Solution {
2public:
3    Node* prevNode;
4    Node* listHead;
5
6    // Main function to convert a BST to a sorted circular doubly-linked list.
7    Node* treeToDoublyList(Node* root) {
8        if (!root) return nullptr;   // If the tree is empty, return nullptr.
9
10        // Reset the prevNode and listHead pointers before starting the DFS.
11        prevNode = nullptr;
12        listHead = nullptr;
13
14        // Perform a depth-first search to traverse the tree in order.
15        DFSInOrder(root);
16
17        // After the DFS is done, connect the head and tail to make it circular.
18        prevNode->right = listHead;
19        listHead->left = prevNode;
20
21        return listHead;    // Return the head of the doubly linked list.
22    }
23
24    // Helper DFS function to perform in-order traversal.
25    void DFSInOrder(Node* currentNode) {
26        if (!currentNode) return;  // Base case: if the current node is null, just return.
27
28        // Traverse the left subtree first (in-order traversal).
29        DFSInOrder(currentNode->left);
30
31        // When processing the current node:
32        if (prevNode) {
33            // If prevNode is not null, link it with the current node.
34            prevNode->right = currentNode;
35            currentNode->left = prevNode;
36        } else {
37            // If this is the leftmost node, it will be the head of the doubly linked list.
38            listHead = currentNode;
39        }
40      
41        // Move prevNode to the current node before traversing the right subtree.
42        prevNode = currentNode;
43
44        // Traverse the right subtree.
45        DFSInOrder(currentNode->right);
46    }
47};
48
1// Definition for a Node.
2class Node {
3    val: number;
4    left: Node | null;
5    right: Node | null;
6
7    constructor(val: number, left: Node | null = null, right: Node | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14/**
15 * Converts a binary search tree to a sorted circular doubly-linked list.
16 * @param {Node | null} root - The root node of the binary search tree.
17 * @returns {Node | null}
18 */
19function treeToDoublyList(root: Node | null): Node | null {
20    if (!root) return root;
21
22    let previous: Node | null = null;
23    let head: Node | null = null;
24
25    /**
26     * Depth-first search (In-order traversal) to iterate over the tree and create the doubly linked list.
27     * @param {Node | null} node - The current node being visited.
28     */
29    function inOrderTraversal(node: Node | null): void {
30        if (!node) return;
31
32        // Traverse the left subtree
33        inOrderTraversal(node.left);
34
35        // Link the current node with the previous node
36        if (previous) {
37            previous.right = node;
38            node.left = previous;
39        } else {
40            // Set the head if this is the leftmost node
41            head = node;
42        }
43      
44        // Move the 'previous' pointer to the current node
45        previous = node;
46
47        // Traverse the right subtree
48        inOrderTraversal(node.right);
49    }
50
51    // Start the in-order traversal
52    inOrderTraversal(root);
53  
54    // Connect the head and tail to make the list circular
55    if (head && previous) {
56        previous.right = head;
57        head.left = previous;
58    }
59
60    return head;
61}
62
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is a good use case for backtracking?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ