VietMX Staff asked 3 years ago
This can be achieved by traversing the tree in the in-order manner that is, left the child -> root ->right node.
In an in-order traversal, first the left sub-tree is traversed, then the root is visited, and finally the right sub-tree is traversed.
One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order traversal of the binary tree, keep inserting each element output into the doubly linked list. But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list in-place i.e. we should not create new nodes for the doubly linked list.
This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified.
- Start with the root node and solve left and right sub-trees recursively
- At each step, once left and right sub-trees have been processed:
- fuse output of left subtree with root to make the intermediate result
- fuse intermediate result (built in the previous step) with output from the right sub-tree to make the final result of the current recursive call
Recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of binary tree h. It will be O(log n) for balanced tree and in worst case can be O(n).
public static void BinaryTreeToDLL(Node root) {
if (root == null)
return;
BinaryTreeToDLL(root.left);
if (prev == null) { // first node in list
head = root;
} else {
prev.right = root;
root.left = prev;
}
prev = root;
BinaryTreeToDLL(root.right);
if (prev.right == null) { // last node in list
head.left = prev;
prev.right = head;
}
}