I am working on a coding challenge. I found a solution, but I did not understand a part of the solution.
The prompt is
Given a binary tree, find the leftmost value in the last row of the tree.
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
Tree is defined:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
This function works (I did not come up with it):
var findBottomLeftValue = function(root) {
var result = root.val;
var resultHeight = 0;
(function recurse (node, height) {
if (node === null) {
return;
}
if (node.left !== null) {
recurse(node.left, height + 1);
}
if (height > resultHeight) {
result = node.val;
resultHeight = height;
}
if (node.right !== null) {
recurse(node.right, height + 1);
}
})(root, 1);
return result;
};
I understand most of the line, but frankly, this is my first time seeing IIFE inside another function, so maybe that threw me off a little.
What I don't understand is, let's say we start with root 1 (using example above), it starts off with node being 1. Since node.left !== null, node is now 2, since node.left !== null, it goes down to 4. node.left is now null, it goes to the next line, which updates height and resultHeight. Then next line, node.right is null, and function ends. In my understanding, it never went to check nodes 3, 5, etc. But the function clearly shows the right answer.
Where on the solution did it check for nodes 3, 5, 6, and 7?
If you imagine what is happening as a stack,it's much easier to understand.
It starts on the node with value 1. When it checks the left node,it's left on hold as the first item of the stack(to be called again when it's the topmost item of the stack again)
It would look something like this when it starts on the second iteration:
2
---
1
Then,it would keep executing and adding to the stack until it check that the node 4 has no left or right node.
At this moment,it would look like this:
4
---
2
---
1
Then,since there's nothing else to do on the node with value 4,it gets removed out of the stack,and then it executes the next topmost of the stack from where it left off:checking the right node of it.
I hope this helped you visualise and understand what really happens because that really helped me and some college coleagues to understand binary trees.