Reverse A Binary Tree (Left to Right)
There are a couple interesting parts to this question. First, since your language is Java, you're most likely to have a generic Node class, something like this:
class Node<T> {
private final T data;
private final Node left;
private final Node right;
public Node<T>(final T data, final Node left, final Node right) {
this.data = data;
this.left = left;
this.right = right;
}
....
}
Secondly, reversing, sometimes called inverting, can be done either by mutating the left and right fields of the node, or by creating a new node just like the original but with its left and right children "reversed." The former approach is shown in another answer, while the second approach is shown here:
class Node<T> {
// See fields and constructor above...
public Node<T> reverse() {
Node<T> newLeftSubtree = right == null ? null : right.reverse();
Node<T> newRightSubtree = left == null ? null : left.reverse();
return Node<T>(data, newLeftSubtree, newRightSubtree);
}
}
The idea of not mutating a data structure is one of the ideas behind persistent data structures, which are pretty interesting.
Reverse a binary tree in O(1) in C/C++.
struct NormalNode {
int value;
struct NormalNode *left;
struct NormalNode *right;
};
struct ReversedNode {
int value;
struct ReversedNode *right;
struct ReversedNode *left;
};
struct ReversedNode *reverseTree(struct NormalNode *root) {
return (struct ReversedNode *)root;
}
You can use recursion. We swap the left and right child of a node, in-place, and then do the same for its children:
static void reverseTree(final TreeNode root) {
final TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
if (root.left != null) {
reverseTree(root.left);
}
if (root.right != null) {
reverseTree(root.right);
}
}
To handle the case where the parameter root
may be null:
static void reverseTree(final TreeNode root) {
if (root == null) {
return;
}
final TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
reverseTree(root.left);
reverseTree(root.right);
}