226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

---
Time - O(n)
Space - O(h)
---

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public TreeNode invertTree(TreeNode root) {
	if (root == null) {
	return null;
	}
	TreeNode temp = root.left;
	root.left = root.right;
	root.right = temp;

	invertTree(root.left);
	invertTree(root.right);

	return root;
	}
	}

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public TreeNode invertTree(TreeNode root) {
	if (root == null) {
	return null;
	}

	Queue<TreeNode> q = new LinkedList<TreeNode>();

	q.offer(root);

	while (!q.isEmpty()) {
	TreeNode node = q.poll();

	TreeNode temp = node.left;
	node.left = node.right;
	node.right = temp;

	if (node.left != null) {
	q.offer(node.left);
	}

	if (node.right != null) {
	q.offer(node.right);
	}
	}

	return root;
	}
	}

	# Definition for a binary tree node.
	# class TreeNode:
	# def __init__(self, val=0, left=None, right=None):
	# self.val = val
	# self.left = left
	# self.right = right
	class Solution:
	def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
	if root is None:
	return

	left = root.left
	root.left = root.right
	root.right = left

	self.invertTree(root.left)
	self.invertTree(root.right)

	return root

SWE Interview preparation