{"id":"5bbf0b05-0801-46c6-904a-9c41aaee2785","name":"Convert Binary Search Tree To Doubly Linked List","description":"1. Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.\r\n2. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. \r\n3. The order of nodes in DLL must be the same as in Inorder for the given Binary Search Tree. The first node of Inorder traversal (leftmost node in BST) must be the head node of the DLL. \r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n Node* left = nullptr;\r\n Node* right = nullptr;\r\n\r\n Node(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nNode* bToDLL(Node* root)\r\n{\r\n return nullptr;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(Node* node)\r\n{\r\n Node* head = node;\r\n while (node != nullptr) {\r\n cout << node.val << \" \";\r\n node = node->right;\r\n if (node == head)\r\n break;\r\n }\r\n}\r\n\r\nNode* constructFromInOrder(vector<int>& inOrder, int si, int ei)\r\n{\r\n if (si > ei)\r\n return nullptr;\r\n int mid = (si + ei) / 2;\r\n Node* root = new Node(inOrder[mid]);\r\n\r\n root->left = constructFromInOrder(inOrder, si, mid - 1);\r\n root->right = constructFromInOrder(inOrder, mid + 1, ei);\r\n\r\n return root;\r\n}\r\n\r\nNode* constructFromInOrder(vector<int>& inOrder)\r\n{\r\n return constructFromInOrder(inOrder, 0, inOrder.size() - 1);\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> in(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> in[i];\r\n }\r\n\r\n Node* root = constructFromInOrder(in);\r\n Node* head = bToDLL(root);\r\n display(head);\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class Node {\r\n int val = 0;\r\n Node left = null;\r\n Node right = null;\r\n\r\n Node(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static Node bToDLL(Node root) {\r\n return null;\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(Node node) {\r\n Node head = node;\r\n while (node != null) {\r\n System.out.print(node.val + \" \");\r\n node = node.right;\r\n if (node == head)\r\n break;\r\n }\r\n\r\n }\r\n\r\n public static Node constructFromInOrder_(int[] in, int si, int ei) {\r\n if (si > ei)\r\n return null;\r\n\r\n int mid = (si + ei) / 2;\r\n Node node = new Node(in[mid]);\r\n\r\n node.left = constructFromInOrder_(in, si, mid - 1);\r\n node.right = constructFromInOrder_(in, mid + 1, ei);\r\n\r\n return node;\r\n }\r\n\r\n public static Node constructFromInOrder(int[] inOrder) {\r\n int n = inOrder.length;\r\n return constructFromInOrder_(inOrder, 0, n - 1);\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] in = new int[n];\r\n for (int i = 0; i < n; i++)\r\n in[i] = scn.nextInt();\r\n\r\n Node root = constructFromInOrder(in);\r\n root = bToDLL(root);\r\n display(root);\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"7\r\n1 2 3 4 5 6 7","sampleOutput":"1 2 3 4 5 6 7 ","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"5c936934-5073-469f-b073-4a05e71ad6a6","name":"Convert Binary Search Tree To Doubly Linked List","slug":"convert-binary-search-tree-to-doubly-linked-list","type":1}],"next":{"id":"a0bb30a7-69b0-41c4-8b8f-5de6e8f94f93","name":"Convert Binary Search Tree To Doubly Linked List","type":0,"slug":"convert-binary-search-tree-to-doubly-linked-list"},"prev":{"id":"b1839e77-0d8d-420e-ba98-54291fde5d06","name":"Burning Tree","type":0,"slug":"burning-tree"}}}

Convert Binary Search Tree To Doubly Linked List

1. Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place. 2. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. 3. The order of nodes in DLL must be the same as in Inorder for the given Binary Search Tree. The first node of Inorder traversal (leftmost node in BST) must be the head node of the DLL.

{"id":"5bbf0b05-0801-46c6-904a-9c41aaee2785","name":"Convert Binary Search Tree To Doubly Linked List","description":"1. Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.\r\n2. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. \r\n3. The order of nodes in DLL must be the same as in Inorder for the given Binary Search Tree. The first node of Inorder traversal (leftmost node in BST) must be the head node of the DLL. \r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n Node* left = nullptr;\r\n Node* right = nullptr;\r\n\r\n Node(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nNode* bToDLL(Node* root)\r\n{\r\n return nullptr;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(Node* node)\r\n{\r\n Node* head = node;\r\n while (node != nullptr) {\r\n cout << node.val << \" \";\r\n node = node->right;\r\n if (node == head)\r\n break;\r\n }\r\n}\r\n\r\nNode* constructFromInOrder(vector<int>& inOrder, int si, int ei)\r\n{\r\n if (si > ei)\r\n return nullptr;\r\n int mid = (si + ei) / 2;\r\n Node* root = new Node(inOrder[mid]);\r\n\r\n root->left = constructFromInOrder(inOrder, si, mid - 1);\r\n root->right = constructFromInOrder(inOrder, mid + 1, ei);\r\n\r\n return root;\r\n}\r\n\r\nNode* constructFromInOrder(vector<int>& inOrder)\r\n{\r\n return constructFromInOrder(inOrder, 0, inOrder.size() - 1);\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> in(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> in[i];\r\n }\r\n\r\n Node* root = constructFromInOrder(in);\r\n Node* head = bToDLL(root);\r\n display(head);\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class Node {\r\n int val = 0;\r\n Node left = null;\r\n Node right = null;\r\n\r\n Node(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static Node bToDLL(Node root) {\r\n return null;\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(Node node) {\r\n Node head = node;\r\n while (node != null) {\r\n System.out.print(node.val + \" \");\r\n node = node.right;\r\n if (node == head)\r\n break;\r\n }\r\n\r\n }\r\n\r\n public static Node constructFromInOrder_(int[] in, int si, int ei) {\r\n if (si > ei)\r\n return null;\r\n\r\n int mid = (si + ei) / 2;\r\n Node node = new Node(in[mid]);\r\n\r\n node.left = constructFromInOrder_(in, si, mid - 1);\r\n node.right = constructFromInOrder_(in, mid + 1, ei);\r\n\r\n return node;\r\n }\r\n\r\n public static Node constructFromInOrder(int[] inOrder) {\r\n int n = inOrder.length;\r\n return constructFromInOrder_(inOrder, 0, n - 1);\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] in = new int[n];\r\n for (int i = 0; i < n; i++)\r\n in[i] = scn.nextInt();\r\n\r\n Node root = constructFromInOrder(in);\r\n root = bToDLL(root);\r\n display(root);\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"7\r\n1 2 3 4 5 6 7","sampleOutput":"1 2 3 4 5 6 7 ","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"5c936934-5073-469f-b073-4a05e71ad6a6","name":"Convert Binary Search Tree To Doubly Linked List","slug":"convert-binary-search-tree-to-doubly-linked-list","type":1}],"next":{"id":"a0bb30a7-69b0-41c4-8b8f-5de6e8f94f93","name":"Convert Binary Search Tree To Doubly Linked List","type":0,"slug":"convert-binary-search-tree-to-doubly-linked-list"},"prev":{"id":"b1839e77-0d8d-420e-ba98-54291fde5d06","name":"Burning Tree","type":0,"slug":"burning-tree"}}}
plane

Editor

Loading...

Convert Binary Search Tree To Doubly Linked List

medium

1. Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place. 2. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. 3. The order of nodes in DLL must be the same as in Inorder for the given Binary Search Tree. The first node of Inorder traversal (leftmost node in BST) must be the head node of the DLL.

Constraints

0 <= Number of Nodes <= 10^9 -10^9 <= value of Node data <= 10^9

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

7 1 2 3 4 5 6 7

Sample Output

1 2 3 4 5 6 7

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode