For the Python solution, there’s unnecessary creation of new Nodes. Instead, we can swap the existing nodes which is more memory efficient. What are others thoughts?
My solution is below for reference. Thanks!
def invert_binary_tree(tree: Node) → Node:
“”"
Outline
- Postorder traversal O(log(h)) h = height of tree,
- O(log(n)) time if balanced
- AND O(n) time if skewed left/right
- Same for space O(log(n)) balanced && O(n) unbalanced (skewed)
“”"
# Empty node
if tree is None:
return
# tree = 1, tree.left = 3, tree.right = 2
# left = 2
# right = 3
# Post order traversal
left = invert_binary_tree(tree.left)
right = invert_binary_tree(tree.right)
# Swap the left and right child
tree.left,tree.right = right,left
return tree # 1
Another good option for this problem, and perhaps the easiest to think about without any recursion, is doing a BFS with a Queue. Add the root to the queue to start, and then run a loop until the queue is empty. On each pass, if either of the children are not None or null or whatever your language uses, then add them to the queue. Swap the current node’s children by simply pointing the left child node to the right child node and vice versa. The loop will then run until the whole tree is inverted.
Java Top down solution:
public static Node invertBinaryTree(Node tree) {
if(tree == null) return null;
Node temp = tree.right;
tree.right = tree.left;
tree.left = temp;
tree.left = invertBinaryTree(tree.left);
tree.right = invertBinaryTree(tree.right);
return tree;
}
The base C# code fails to compile. Can someone fix it please? Thanks.
Actually not, it is still an issue. And in Insert Into BST I’ve described by comment to Mark’s comment what is wrong.
Fix it please.
Btw, resulted solution not in-place (as it stated in task) you create a new tree instead of retarget the links.
for C++:
Node* invert_binary_tree(Node* tree) {
// WRITE YOUR BRILLIANT CODE HERE
if(tree == nullptr) return nullptr;
invert(tree);
return tree;
}
void invert(Node* node)
{
if(node == nullptr) return;
invert(node->left);
invert(node->right);
std::swap(node->left, node->right);
}
sorry, I’m not sure why the code was formatted that way when I hit comment
You can change the line in Main → System.out.println(String.join(" “, res)); TO System.out.println(String.join(” ", resArr));
“You guys should seriously stop using C++, switch to Rust, C++ is used so little nowadays, its not the 90s anymore”
function invertBinaryTree(tree) {
if (tree === null) return null;
function dfs(node) {
[node.left, node.right] = [node.right, node.left];
if (node.left) dfs(node.left);
if (node.right) dfs(node.right);
}
dfs(tree);
return tree;
}
Easy to understand
Node<int>* invertTree(Node<int>* root, Node<int>* left, Node<int>* right) {
// WRITE YOUR BRILLIANT CODE HERE
Node<int>* leftTree = root->left;
Node<int>* rightTree = root->right;
if(leftTree != NULL) {
invertTree(leftTree, leftTree->left, leftTree->right);
}
if(rightTree != NULL) {
invertTree(rightTree, rightTree->left, rightTree->right);
}
root->left = rightTree;
root->right = leftTree;
return root;
}
Node<int>* invert_binary_tree(Node<int>* root) {
// WRITE YOUR BRILLIANT CODE HERE
if(root == NULL) return NULL;
return invertTree(root, root->left, root->right);
}
I did this (Python) and it works. Is the solution creating an entirely new tree that is inverted or am i not understanding?
def invert_binary_tree(tree: Node) → Node:
if not tree:
return tree
if not tree.left and not tree.right:
return tree
tree = swap_children(tree)
invert_binary_tree(tree.right)
invert_binary_tree(tree.left)
return tree
def swap_children(node):
temp = node.left
node.left = node.right
node.right = temp
return node
well guess I dont know how to format for this lol.
public static Node<Integer> invertBinaryTree(Node<Integer> tree) {
// WRITE YOUR BRILLIANT CODE HERE
if(tree == null) return null;
Node<Integer> temp = tree.left;
tree.left = invertBinaryTree(tree.right);
tree.right = invertBinaryTree(temp);
return tree;
}
So my following code works for the matching leetcode question #226, but doesn’t work here??
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root):
if not root:
return None
temp = root.left
root.left = root.right
root.right = temp
dfs(root.left)
dfs(root.right)
return root
return dfs(root)
In Place invert
public static Node<Integer> invertBinaryTree(Node<Integer> tree) {
if(tree == null){
return null;
}
Node<Integer> tmp = tree.left;
tree.left = invertBinaryTree(tree.right);
tree.right = invertBinaryTree(tmp);
return tree;
}
you have to assign the result of your dfs calls to the left/right variables:
root.left = dfs(root.left)
root.right = dfs(root.right)
return root
Why would that be the case?
The confusing part of this is that the example is not part of the test cases. It took me a while to figure that out - also, it is about inverting a BT not a BST (curious why is this challenge in this chapter).