Convert Binary Search Tree To Sorted Doubly Linked List - Leetcode Solution

Problem Statement: Given a Binary Search Tree (BST), convert it to a sorted doubly linked list. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted Doubly Linked List. The order of nodes in Doubly Linked List must be the same as inorder traversal of the given Binary Search Tree. The first node of Inorder traversal (leftmost node in BST) must be the head node of the Doubly Linked List.

Example: Input: 4 /
2 5 /
1 3

Output: 1<->2<->3<->4<->5

Solution: This problem can be solved using recursion. At each node of the tree, we will recursively create two sorted doubly linked lists: one for the left subtree and one for the right subtree. We will then merge these two lists with the current node to get the final sorted doubly linked list.

To merge the two sorted doubly linked lists, we will make the maximum node in the left subtree point to the current node as its next pointer, and the minimum node in the right subtree point to the current node as its previous pointer.

We will maintain a global variable called last, which will keep track of the last node added to our doubly linked list. We will update this variable as we add nodes to the list.

The base case for the recursive function is when the node is null, in which case we simply return.

Code:

public Node treeToDoublyList(Node root) { if (root == null) return null; Node last = null; Node head = treeToDoublyListHelper(root, last); // connect head and tail head.left = last; last.right = head; return head; }

private Node treeToDoublyListHelper(Node node, Node last) { if (node == null) return null; Node left = treeToDoublyListHelper(node.left, last); if (left != null) { last.right = node; node.left = last; } else { // if left is null, this is the first node in the list last = node; head = node; } last = node; Node right = treeToDoublyListHelper(node.right, last); return head; }

In the main function, we first check if the input root is null. If it is, we simply return null.

We then create a last node variable and a head node variable.

We call a recursive function treeToDoublyListHelper on the root node and pass in the last node variable. This function returns the head of the doubly linked list.

We then connect the head and tail of the list (which are stored in the last variable) and return the head.

The recursive function takes in two parameters: the current node and the last node added to the list.

If the current node is null, we simply return null.

We then recursively call the function on the left subtree of the current node and pass in last as the second parameter. This returns the head of the doubly linked list for the left subtree.

If the left subtree list is not empty, we connect the last node of the left subtree list to the current node, and vice versa.

If the left subtree list is empty, this means that the current node is the first node in the list, so we set the last node variable to the current node and update the global head variable to the current node.

We then update the last node variable to the current node and recursively call the function on the right subtree. We pass in last as the second parameter to keep track of the last node added to the list.

Finally, we return the head of the doubly linked list.

Complexity Analysis: Time Complexity: O(n) where n is the number of nodes in the tree. We visit each node exactly once. Space Complexity: O(n) because of the recursive call stack.

1