Invert Binary Tree

Problem:

Invert a binary tree.

For example:

Given:

     5

   /   \

  2     8

 / \   / \

1   3 6   9

Answer:

     5

   /   \

  8     2

 / \   / \

9   6 3   1

Solution:

We can use recursive approach, at each level, we recursively swap the left and right node. The time complexity is O(N). We are using in place swap, so we don't have to store another tree, the space complexity is dominated by the function calling stack, at each call, there are a few variables. So the space cost is O(H), where H is the height of the tree.

class Solution {
  public static void main(String...args) {
    Node root = new Node(5, new Node(2, new Node(1, null, null), new Node(3, null, null)),
                        new Node(8, new Node(6, null, null), new Node(9, null, null)));
    printInorder(root);
    System.out.println();
    invert(root);
    printInorder(root);
    System.out.println();
  }
  private static Node invert(Node root) {
    if(root == null) return null;
    Node tmp = root.left;
    root.left = invert(root.right);
    root.right = invert(tmp);
    return root;
  }
  private static void printInorder(Node root) {
    if(root == null) return;
    printInorder(root.left);
    System.out.print(root.value + " ");
    printInorder(root.right);
  }
 
  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

Time complexity O(N), space complexity O(H).