Interview Questions

Microsoft Interview Question for Software Engineers about Coding, Data Structures, Algorithms Data Structures Trees and Graphs

Microsoft Interview Questions and Answers


(Continued from previous question...)

Microsoft Interview Question for Software Engineers about Coding, Data Structures, Algorithms Data Structures Trees and Graphs

Question1:
Convert a binary search tree to a sorted doubly linked list in O(n) time and in place. Manipulate the existing tree. Donot create a new tree.


maybe an answer:
Do an in-order traversal of the binary tree, at each node joining the linked list resulting from the left and right children.

public static Node[] createLinkedList(Node root) {
if (root == null) return new Node[] {null, null};
Node[] result = new Node[2];
if (root.leftChild != null) {
Node[] leftList = createLinkedList(root.leftChild);
root.previous = leftList[1];
root.previous.next = root;
result[0] = leftList[0];
} else result[0] = root;
if (root.rightChild != null) {
Node[] rightList = createLinkedList(root.rightChild);
root.next = rightList[0];
root.next.previous = root;
result[1] = rightList[1];
} else result[1] = root;
return result;
}

(Continued on next question...)

Other Interview Questions