# Java One Recursive Solution and Two Iterative Solutions (DFS, BFS) With Explanations

• Solution 1: Recursive Solution

``````// Method 1: Recursive Solution
// Time: O(n)
// Space: O(height)
public TreeNode invertTree(TreeNode root) {
// Base case
if (root == null) {
return null;
}
// Store references for root.left and root.right
final TreeNode left = root.left;
final TreeNode right = root.right;
// invert right subtree, and make it the left subtree of root
root.left = invertTree(right);
// invert left subtree, and make it the right subtree of root
root.right = invertTree(left);
return root;
}
``````

Solution 2: Iterative DFS

``````// Method 2: Iterative DFS
// Time: O(n)
// Space: O(height)
public TreeNode invertTree(TreeNode root) {
// Corner case
if (root == null) {
return null;
}

// Use a stack to help DFS
stack.offerLast(root);

while (!stack.isEmpty()) {
TreeNode cur = stack.pollLast();
// invert left and right subtrees of cur
TreeNode left = cur.left;
cur.left = cur.right;
cur.right = left;
// offer left and right nodes to stack so that they can invert their subtrees
if (cur.left != null) {
stack.offerLast(cur.left);
}
if (cur.right != null) {
stack.offerLast(cur.right);
}
}

return root;
}
``````

Solution 3: Iterative BFS

``````// Method 3: Iterative BFS
// Time: O(n)
// Space: O(n)
public TreeNode invertTree(TreeNode root) {
// Corner case
if (root == null) {
return null;
}

// Use a stack to help DFS
queue.offer(root);

while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
// invert left and right subtrees of cur
TreeNode left = cur.left;
cur.left = cur.right;
cur.right = left;
// offer left and right nodes to stack so that they can invert their subtrees
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}

return root;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.