Given two binary search trees, merge them into a doubly-linked list in sorted order.
For example,
Input: Below BSTs
20
/\
1030
/\
25100
50
/\
570
Output: Below DDL
5 > 10 > 20 > 25 > 30 > 50 > 70 > 100 > null
20
/\
1030
/\
25100
50
/\
570
Output: Below DDL
5 > 10 > 20 > 25 > 30 > 50 > 70 > 100 > null
Practice this problem
The idea is to convert each binary search tree into a doubly-linked list first in sorted order and then merge both lists into a single doubly linked list in sorted order.
To convert a binary search tree into a doubly-linked list in sorted order, perform reverse inorder traversal on the BST. In the reverse inorder traversal, the right child for a node is processed before its left child. We insert the node at the front of the doubly linked list for each encountered node in the reverse inorder traversal. The reverse inorder traversal is used to ensure the correct insertion order in the doubly linked list since the reverse inorder traversal visits the nodes of a BST in the decreasing order.
This is demonstrated below in C++, Java, and Python:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | #include using namespace std; // Data structure to store a BST node struct Node { int data; Node* left, *right; // Constructor Node[int data] { this->data = data; this->left = this->right = nullptr; } }; // Helper function to print a doubly linked list void printDoublyLinkedList[Node* head] { while [head] { cout right, headRef]; // push the current node at the front of the doubly linked list push[root, headRef]; // recursively convert the left subtree convertBSTtoDLL[root->left, headRef]; } // Recursive function to merge two doubly-linked lists into a // single doubly linked list in sorted order Node* mergeDDLs[Node* a, Node* b] { // if the first list is empty, return the second list if [a == nullptr] { return b; } // if the second list is empty, return the first list if [b == nullptr] { return a; } // if the head node of the first list is smaller if [a->data data] { a->right = mergeDDLs[a->right, b]; a->right->left = a; return a; } // if a head node of the second list is smaller else { b->right = mergeDDLs[a, b->right]; b->right->left = b; return b; } } // Function to merge two binary search trees into a doubly-linked list // in sorted order Node* merge[Node* a, Node* b] { // convert the first binary search tree into a doubly-linked list Node* first = nullptr; convertBSTtoDLL[a, first]; // convert the second binary search tree into a doubly-linked list Node* second = nullptr; convertBSTtoDLL[b, second]; // merge both doubly-linked lists return mergeDDLs[first, second]; } int main[] { /* Construct the following BST 20 /\ 1030 /\ 25100 */ Node* a = new Node[20]; a->left = new Node[10]; a->right = new Node[30]; a->right->left = new Node[25]; a->right->right = new Node[100]; /* Construct the following BST 50 /\ 5 70 */ Node* b = new Node[50]; b->left = new Node[5]; b->right = new Node[70]; // merge both BSTs into a doubly-linked list Node* root = merge[a, b]; printDoublyLinkedList[root]; return 0; } |
DownloadRun Code
Output:
5 > 10 > 20 > 25 > 30 > 50 > 70 > 100 > null
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | // A class to store a BST node class Node { int data; Node left, right; // Constructor Node[int data] { this.data = data; this.left = this.right = null; } } class Main { // Helper function to print a doubly linked list public static void printDoublyLinkedList[Node head] { while [head != null] { System.out.print[head.data + " > "]; head = head.right; } System.out.println["null"]; } // Function to insert a BST node at the front of a doubly linked list public static Node push[Node root, Node head] { // insert the given node at the front of a DDL root.right = head; // update the left child of the existing head node of the DDL // to point to the BST node if [head != null] { head.left = root; } // update the head pointer of DDL head = root; return head; } // Recursive function to convert a BST into a doubly-linked list. It takes // the BST's root node and the head node of the doubly linked list as an argument public static Node convertBSTtoDLL[Node root, Node head] { // Base case if [root == null] { return head; } // recursively convert the right subtree head = convertBSTtoDLL[root.right, head]; // push the current node at the front of the doubly linked list head = push[root, head]; // recursively convert the left subtree head = convertBSTtoDLL[root.left, head]; return head; } // Recursive function to merge two doubly-linked lists into a // single doubly linked list in sorted order public static Node mergeDDLs[Node a, Node b] { // if the first list is empty, return the second list if [a == null] { return b; } // if the second list is empty, return the first list if [b == null] { return a; } // if the head node of the first list is smaller if [a.data 10 > 20 > 25 > 30 > 50 > 70 > 100 > null Python
|