Binary Tree Level Order Traversal

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

• 102. Binary Tree Level Order Traversal (Medium).

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

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

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

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.

Next Steps

• (High Priority) Redo this problem in Rust! Leetcode offers Rust as a language.
• (Med Priority) Analyze space complexity.

• (Med Priority) Do the other 3 questions from the original post