Reverse A Binary Tree (Left to Right) [closed]

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);}

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;}

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.