Discussing Coding Interview Questions from Google, Amazon, Facebook, Microsoft, etc. The reason is that we are going to change where pLastNodeInList points. Here is another solution in java package com. Can this code be done as: We keep deleting the root and keep inserting it again till the left child of the root becomes null. Feeling good to share the link to practice c interview questions http: I came up with a simpler approach when I set out to solve the same problem: Hope this helps someone.

Hi it may sound basic question but when current reaches left last node how does the node reaches its root?? Modified version, which will remove the extra traversal in tree to find the head node. Seems unnecessary, as pLastNodeInList would not be NULL at that stage.

This comment has been removed by the author. Here is an alternate solution in java where we keep passing leftParent and rightParent and correct the left and right pointers.

c# - Interview Question - Binary Search Tree - Stack Overflow

Let me know if you see any issue with this solution: Friday, September 9, No. Convert a binary search tree to a sorted double-linked list.

We can only change the target of pointers, but cannot create any new nodes. For example, if we input a binary search tree as shown on the left side of the Figure 1, the output double-linked list is shown on the right side. The conversion between a binary search tree and a sorted double-linked list. In a binary tree, each node has two pointers to its children.

In a double-linked list, each node also has two pointers, one pointing to the previous node and the other pointing to the next one.

Additionally, binary search tree is a sorted data structure. In a binary search tree, value in parent is always greater than value of its left child and less than value of its right child. Therefore, we can adjust a pointer to its left child in binary search tree to its previous node in a double-linked list, and adjust a pointer to its right child to its next node.

It is required that the converted list should be sorted, so we can adopt in-order traversal. Binary search tree interview questions in c is because according to the definition of in-order traversal we traverse from nodes with less value to binary search tree interview questions in c with greater value.

When we reach the root of the binary tree in Figure1, the tree may be viewed start trader forex nowy target three parts: According to the definition of sorted double-linked list, the root macgruber stock market crash with value us gaap stock compensation should be linked to the node with the greatest value the node with value 8 in its left sub-tree, and it should be also linked alpari uk is binary option trading signals a scam the node with the least value the node with value 12 in its right sub-tree, as shown in Figure 2.

A tree with three parts: After we can the left sub-tree and right sub-tree, and we link them with the root, and then we can get a sorted double-linked list. According to the definition of in-order traversal, the sub-tree should be already converted to a sorted list when we reach its root the node with value 10and the last node in the sorted list should be the node with the greatest node the node with value 8.

If we link the last node in list to the root node of tree, then the root is the last node in list now.

Top 25 Interview Questions - GeeksforGeeks

We continue to convert its right sub-tree, and connect the root to the node with its least value. How to convert its left sub-tree and right sub-tree?

It should be similar to converting the whole tree. Therefore, we can solve it with recursion. In the code above, pLastNodeInList is the last node also the node with the greatest value in the converted double-linked list. When we reach the value with 10, its left sub-tree has already been converted, and pLastNodeInList points to the node with 8. Afterwards we connect the root node to the linked list, and the node with 10 becomes the last node in the list new node with the greatest valueso we move the pointer pLastNodeInList to the node with We continue to invoke the function recursively with parameter pLastNodeInList to convert the right sub-tree.

After we reach the left most node in the right sub-tree also the node with least valuewe linked it to the node with 10 in the list. You may find the details of this book on Amazon. The author Harry He owns all the rights of this post. If you are going to use it in your books, please contact me zhedahht gmail. Posted by Harry He at 7: Share to Twitter Share to Facebook Share to Pinterest.

Binary Search TreeData StructureDouble-linked ListInterview QuestionMicrosoft. Please explain ', 'timestamp': Harry He March 14, at Bikash January 22, at 2: Kulbhushan Arora March 20, at Ajay Gaur May 29, at 6: Savan July 2, at Krishna Mohan August 20, at 6: Thirumal Venkat October 12, at 8: Venkatesh December 18, at Charlie P January 20, at 6: Unknown January 24, at 9: Bahman Engheta January 24, at Swapnil October 8, at 2: My Book Has Been Published Coding Interviews: Click the cover image to view the details on Amazon.

Pages Blog Home Coding Interviews: About Me Harry He.