Invert Binary Tree (left && right)
Given the root of a binary tree, invert the tree, and return its root.
public TreeNode invertTree(TreeNode root) {
//base case
if(root==null){
return null;
}
root.right = invertTree(root.left);
root.left = invertTree(root.right);
return root;
}
At first for couple of weeks I thought this was the solution. But I was wrong. I made a mistake writing this code and I realize it is wronf when I run this code. In the beginning I didn’t see what’s wrong with it.Then I asked to ChatGPT and here is the answer:
The problem in your code lies in the fact that you’re immediately assigning root.right before inverting root.left, which leads to an issue where you lose track of the original root.right before swapping it. This results in incorrect swapping of left and right subtrees.
Issue:
- When you assign
root.right = invertTree(root.left);, you overwrite the original right subtree. - When you later try to invert the left subtree with
root.left = invertTree(root.right);,root.righthas already been modified.
Fix:
To fix this, you need to store the original left and right subtrees in temporary variables before swapping them. This way, you don’t lose the reference to the original subtrees.
Corrected code
public TreeNode invertTree(TreeNode root) {
// base case
if (root == null) {
return null;
}
// store the original left and right
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
// swap left and right
root.left = right;
root.right = left;
return root;
}
Similarity between this and merge tree question
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
