Given a binary tree, convert it into a doubly linked list as described: 1. We do not have to create a new linked list data structure. We have to convert the tree to a doubly linked list. 2. The doubly linked list should be created such that nodes follow inorder traversal of the binary tree. 3. Left node of the binary tree should be converted to the previous node of the doubly linked list. 4. Right node of the binary tree should be converted to the next node of the doubly linked list. 5. Left most node of the binary tree should be the head of the linked list.
Example: Tree: 1 2 3 4 5 6 7
Output: 4 <-> 2 <-> 5 <-> 1 <-> 6 <-> 3 <-> 7
Question Asked in
Amazon, Facebook, Microsoft, Adobe
Video coming soon!
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
Process left subtree first: 1. Move to the right most node of left subtree to get the inorder predecessor of the root, lets call is A. 2. Now create doubly linked list pointers: a. Set the A.right to the root. b. Set root.left to A. Process right subtree: 1. Move to the left most node of right subtree to get the inorder successor of the root, lets call is B. 2. Now create doubly linked list pointers: a. Set the B.left to the root. b. Set root.right to B. Please go through algorithm visualization section and java code in code snippet section.
Support us by whitelisting IDeserve in your ad-blocker.