Grind 75 Question 6: Invert Binary Tree
At last, the infamous Invert Binary Tree question…
The Problem
Given the root of a binary tree, invert the tree, and return its root.
The First Attempts
The first thing I need to figure out is, what is a binary tree? And how in the world does one invert it? I guess I’ll spend the next day or so finding out…
I know I can’t just whiteboard this, so I see how far I can get using the Merge Linked List solution as a guide.
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
let invertedTree = new TreeNode();
while (root) {
invertedTree.val = root.val;
invertedTree.left = root.right;
invertedTree.right = root.left;
root = root.next;
}
return invertedTree
};That code actually, surprisingly, somewhat works. It gets me halfway there. Well, maybe…a quarter of the way. It inverts part of the tree, but not the children: for an input of [4,2,7,1,3,6,9] the output is [4,7,2,6,9,1,3], while it should be [4,7,2,9,6,3,1]. So the root stays the same, the first children are inverted, and after that…the children stay in the same place (but attached to the correct parent nodes).
So, off to Neetcode I go.
Neetcode explains the part I was missing: it needs to be done recursively. So a function is called within the function, so that all nodes are touched and swapped. My code is ripped straight from someone else’s Javascript code in the Leetcode forum, but I think I can explain it. Here it is:
The Solution
var invertTree = function(root) {
if(!root) return root;
function traverse(node) {
if (!node) return null;
const newNode = { val: node.val };
newNode.left = traverse(node.left);
newNode.right = traverse(node.right);
let temporary = newNode.left;
newNode.left = newNode.right;
newNode.right = temporary;
return newNode;
}
return traverse(root);
};So basically, here’s the walkthrough of all that up there:
- If there is no root, just return the root, which will be [].
- Otherwise, here’s a new function to perform on root!
- If the node being looked at doesn’t exist, return null.
- Otherwise, let’s create a newNode, whose value is the value of the node being looked at.
- The left node of that new node will be — heyo! THIS VERY FUNCTION, performed on the left node of the current node being looked at. This is the sauce. It basically means the entire tree is traversed down until it reaches the bottom.
- Once we’re done traversing, we do the swapping. We first store the copied left node in a temporary variable, since we’ll need it in a second. Then we say, “Hey, left node? Your value is now right node. Right node? You get what’s in temporary.” Ba-boom. A swap. newNode is returned, and we move on with our day.
I’m still not entiiiiirely sure how it knows when to stop swapping, but there we go. An inverted binary tree.
What I Learned
- All about binary trees! There are roots, left nodes, right nodes, and each node has its own node. I mean, I’d watched the Back to Back SWE YouTube video explanation before, but this was the first time I’d ever coded with one.
- What exactly a recursive function is. A function inside a function! Gets the job done. Somehow. Onto Question 7! Why, at this pace I’ll be ready for my interview come next Christmas. No, not the Christmas coming up in 5 months. Christmas of 2023. Jingle bells and ho ho ho.
mins
read
