leetcode month day 3: invert binary tree

The classic whiteboard problem.

I chose the “busy software engineer” approach: I know an algorithm that will work and is trivial to implement. Implement that.

To remind everyone what inverting a tree is: if criterion for insertion is left branch < right, then then output tree should have left branch > right. The dead simple algorithm is top-down: save the left, assign the right to the left, assign the saved to the right, recurse.

It’s clear, it’s simple, and fast to code. I literally had a working solution in 2 runs (forgot the null root case on the first run).

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    invertTree(root.Left)
    invertTree(root.Right)

    t := root.Left
    root.Left = root.Right
    root.Right = t
    
    return root
}

About as simple as you can possibly get. Scorewise, it’s fast: top 77%. Memorywise, it’s pretty poor: bottom 8%.

I’m betting a pointer crawl would use less memory but wouldn’t necessarily be that much faster. Let’s see.

First note, still writing append as if this were Scala. Sigh.

This try ends up in an infinite loop; I’m mismanaging the stack somehow. (See why letting Go do it is better?) I’m declaring this good enough and moving on. I expect I could write a version where I manage the stack myself, but this is why we invented higher-level languages.

Unless our trees are always incredibly deep, this is the right way to do this. Even skipping the recursion for nil subtrees doesn’t really make it faster.

On the other hand, I solved the initial recursive version in about 5 minutes, so I’m getting my feet back under me.