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
|