RJ
BAN USERHere's another recursive implementation in Java:
public Node<T> transformToRight(Node<T> node) {
if (node == null) {
return null;
}
if(node.left == null) {
return node;
}
Node<T> leftSubtree = transformToRight(node.left);
Node<T> rightSubtree = transformToRight(node.right);
// Move left subtree to the right of the current root
node.right = leftSubtree;
// Traverse the leftsubtree till the last node. And set right child as the right child of current root
while (leftSubtree.right != null)
leftSubtree = leftSubtree.right;
leftSubtree.right = rightSubtree;
return node;
}
The idea is like this:
1. For each node, we call transform on it's left and right node. As we do have to transform both the subtrees.
2. Once we have the left subtree and right subtree transformed, we add the left subtree in between the parent and the right subtree. Note, we have to set the parent.next = leftsubtreeroot, and traverse the left subtree till we reach the leaf, and set the next of that leaf to the parent.right
I don't really understand what are restricted to use by saying no extra space. Because in Java, a String is immutable, so we have to create a character array from the given String, and create a String back from the modified character array. If those are the valid usage of extra memory, then here's my implementation in Java.
I've explained the code with appropriate comment, in case anyone needs an explanation:
- RJ December 11, 2013