SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

Invert a Binary Tree Visualizer

At each node, swap its left and right children, then invert both subtrees. An empty tree is already inverted.

Start the Invert a Binary Tree simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Call invertTree(50).
  2. Swap the children of 50: left is now 70, right is now 30.
  3. Call invertTree(70).
  4. Swap the children of 70: left is now 80, right is now 60.
  5. Call invertTree(80).
  6. 80 is a leaf: both children are null, nothing to swap.
  7. 80 and everything below it are mirrored.
  8. Call invertTree(60).
  9. Swap the children of 60: left is now 65, right is now null.
  10. Call invertTree(65).
  11. 65 is a leaf: both children are null, nothing to swap.
  12. 65 and everything below it are mirrored.
  13. 60 and everything below it are mirrored.
  14. 70 and everything below it are mirrored.
  15. Call invertTree(30).
  16. Swap the children of 30: left is now 40, right is now 20.
  17. Call invertTree(40).
  18. Swap the children of 40: left is now null, right is now 35.
  19. Call invertTree(35).
  20. 35 is a leaf: both children are null, nothing to swap.
  21. … 4 more steps …
  22. 20 and everything below it are mirrored.
  23. 30 and everything below it are mirrored.
  24. 50 and everything below it are mirrored.
  25. Done. An inorder walk now reads 80, 70, 65, 60, 50, 40, 35, 30, 20: largest first.

Try it with your own input →

Invert a binary tree in Java, Python, C++, C and JavaScript

TreeNode invertTree(TreeNode node) {
  if (node == null) return null;
  TreeNode tmp = node.left;
  node.left = node.right;
  node.right = tmp;
  invertTree(node.left);
  invertTree(node.right);
  return node;
}
def invert_tree(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    invert_tree(node.left)
    invert_tree(node.right)
    return node
TreeNode* invertTree(TreeNode* node) {
  if (!node) return nullptr;
  TreeNode* tmp = node->left;
  node->left = node->right;
  node->right = tmp;
  invertTree(node->left);
  invertTree(node->right);
  return node;
}
struct TreeNode* invertTree(struct TreeNode* node) {
  if (node == NULL) return NULL;
  struct TreeNode* tmp = node->left;
  node->left = node->right;
  node->right = tmp;
  invertTree(node->left);
  invertTree(node->right);
  return node;
}
function invertTree(node) {
  if (node === null) return null;
  const tmp = node.left;
  node.left = node.right;
  node.right = tmp;
  invertTree(node.left);
  invertTree(node.right);
  return node;
}

In an interview

LeetCode 226, Invert Binary Tree: mirror the tree so every left child becomes a right child.

Preorder, postorder or a BFS queue all work, because each swap only touches one node. After inverting a BST, an inorder walk gives the values in descending order.

More trees