leetcode day 28: not finishing this month, and tree diameter

First: other projects popped their heads in: setting up a friend’s Etsy store, an announcement from Apple that I had 30 days to update an app before it was pulled, and the holidays. So I really haven’t touched the challenge since the 16th, or about ten days ago, and finishing all 75 problems in a month was already quite the challenge.

The store is up and has had some orders already, and the app has been brought forward from Swift 3 to Swift 5, and updated to Xcode 15 (which ChatGPT cheerily insists doesn’t exist unless you pay money for its dubious advice at the ChatGPT 4 level). So let’s get back into the challenges.

Another tree problem; this one requires us to find the longest leaf-to-leaf path in the tree, not necessarily going through the root. I struggled with this one a while, but did not hit on the need to have the current largest diameter outside of crawl; I eventually gave up and Googled a solution, which passed a pointer to the diameter into the crawler, so we always were looking at the absolute maximum across the whole tree.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func diameterOfBinaryTree(root *TreeNode) int {
    diameter := 0;
    _ = crawl(root, &diameter);
    return diameter;
};

func crawl(root *TreeNode, diameter *int) int {
        if root == nil {
            return 0
        }
        leftSubtreeDepth := crawl(root.Left, diameter)
        rightSubtreeDepth := crawl(root.Right, diameter)
        *diameter = max(*diameter, leftSubtreeDepth + rightSubtreeDepth)
        return max(leftSubtreeDepth, rightSubtreeDepth) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

This was 100% on speed, and 20% on memory.

I was close; I had the nil root case, and I’d figured out I needed the depths of the trees, but I didn’t put together that I’d need to cache the diameter completely outside the crawler to accurately find the maximum – if you just pass it back recursively, a larger value can end up discarded.