After a pretty stressful day at work - getting assigned a drop everything and shift gears to ‘this’ type of task - I went to Central Rock Climbing Gym to de-stress through climbing… but only to get more stressed. (I’m going to Hueco Tanks, TX in 2 weeks and I’ve basically neglected any sort of real preparation…)
On the 9:48PM LIRR ride back to Bayside, I went through my usual twitter browsing (99% developer stuff) and came across one post that seriously got my heart racing & anxiety sky rocketing…
Did some coding
Got home. Beat 1 run of “The Binding of Isaac” and went straight to Leetcode. I clicked one anonymous post, and went to the Round 1 Question that was posted
Fast forward about 5 minutes. My code passed.
Wait.
What?
🥳🥳🥳 As someone who mostly derps around with web stuff, it was cool to see progress here.
Thought process
Recursive Helper
My initial thought was that a recursive helper function would get the job done (they usually do in binary tree problems).
Push onto an array
If they wanted me to turn:
3
/ \
9 20
/ \
15 7
into:
[
[3],
[9,20],
[15,7]
]
My thought was to push node values onto the various arrays at each depth.
I’d also have to check that if there isn’t already an array at a given depth, initialize it to []
.
Pass depth as state
I’d need to keep track of depth and I can do so by passing it down as ‘state’, or an extra argument to the recursive helper function.
First run
(Don’t worry about var
, let
, const
.)
var levelOrder = function (root) {
let traversed = []
var helper = (node, depth) => {
if (!node) return
if (typeof traversed[depth] !== "Array") {
traversed[depth] = []
}
traversed[depth].push(node.val)
helper(node.left, depth + 1)
helper(node.right, depth + 1)
}
helper(root, 0)
}
Result
Wrong Answer | |
---|---|
Runtime | 92 ms |
Your input | [3,9,20,null,null,15,7] |
Output | undefined |
Expected | [[3],[9,20],[15,7]] |
I simply didn’t return the traversed
array value that I wanted to return.
Second run
var levelOrder = function (root) {
let traversed = []
var helper = (node, depth) => {
if (!node) return
if (typeof traversed[depth] !== "Array") {
traversed[depth] = []
}
traversed[depth].push(node.val)
helper(node.left, depth + 1)
helper(node.right, depth + 1)
}
helper(root, 0)
return traverse // <--- added this
}
Result
Wrong Answer | |
---|---|
Runtime | 128 ms |
Your input | [3,9,20,null,null,15,7] |
Output | [[3],[20],[7]] |
Expected | [[3],[9,20],[15,7]] |
I knew I wasn’t 100% sure on the expected value from typeof
an array
if (typeof traversed[depth] !== "Array")
So I had to consult MDN typeof
docs.
console.log(typeof ["blubber"])
// "object" 🤷🏻♂️
Third run and solution
var levelOrder = function (root) {
let traversed = []
var helper = (node, depth) => {
if (!node) return
// fixed this
if (typeof traversed[depth] !== "object") {
traversed[depth] = []
}
traversed[depth].push(node.val)
helper(node.left, depth + 1)
helper(node.right, depth + 1)
}
helper(root, 0)
return traversed
}
Result
Accepted | |
---|---|
Runtime | 64 ms |
Your input | [3,9,20,null,null,15,7] |
Output | [[3],[9,20],[15,7]] |
Expected | [[3],[9,20],[15,7]] |
Time Complexity
We’re traversing the tree, and visting each node once, so O(n)
is the Time Complexity
Space Complexity
🤦🏻♂️ I still don’t know how to analyze this. @ ME ON TWITTER and let me know how.