Tag Archives: trees

Musings, Projects

Demonstrative Implementation: LZW

There’s something of the “standard literature” in undergraduate algorithms: graph traversals, greedy and dynamic programming, sorts and data structures, and so on. One class of algorithms that seems oddly excluded, at least from my experience, is compression algorithms. So I wanted to explore more of that, in this case by implementing LZW.

I implemented (I think…) a more-or-less standard LZW algorithm here. Continuing my theme of bridging computer science and practice (started (?) with my Bloom filter write-up I wrote it in C, and

Some take-aways:

  • I didn’t really bother with literate coding. I think that was ultimately the right thing to do. Uh oh.
  • My biggest frustration with example implementations online (that I can find, mainly from Wikipedia: there’s an old Dr. Dobbs article, and then a million Rosetta Code implementations all doing the same thing) is that it doesn’t seem to reflect a practical implementation. A linear scan over the dictionary? I know (better than most, I think…) that linear scans are great, but it’s hard to believe that’s the right thing here.
  • The Sedgwick implementation for his undergrad book seems OK.
  • I think I can make an interesting short-course on how I iteratively improved performance.
  • I really dropped the ball implementing clear-codes, that was a mess and a half. But it’s exactly the complications of “really” implementing clear-codes, variable-length coding, and so on that I am frustrated being skimmed over by academic resources! Absent my efforts (such that they are) it seems the students’ options are to ignore them entirely, or dive into gzip’s source base.

I have a PDF with more thoughts here: https://github.com/agorenst/lzw/blob/master/lzw.pdf ; you can see how I’m trying to get the framing.

Binary Search Tree, Binary Tree, Interview Questions

Trim a Binary Search Tree (Leetcode 32)

Another one from the archives. Similar to the merge-binary-trees question, I think this is a nice exercise for students are starting to feel comfortable with the “classic” questions. I think this problem has some natural-enough motivation, and for the student to be confident in their solution, they’d need to be confident in their recursive reasoning.

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root is None: return None
        if root.val < low: return self.trimBST(root.right, low, high)
        if root.val > high: return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

Discussion Points

  1. We still have that classic “skeleton” of handling-the-base-case, and then building up our solution from smaller trees (recursive calls).
  2. I think the big conceptual jump is the confidence of being able to return the empty tree (None or null or whatever) even when the tree isn’t “originally” the empty tree, and know that it will percolate up correctly in the previously recursive invocations.
  3. As always it’s not that this problem literally comes up in practice, but taking some “database” and preprocessing it according to some later filter is good. For people who have a passion for functional programming, this is nothing but a particular filter applied to a tree instead of a list.

In fact as I think about it, the idea of this being a tree filter may be a particularly compelling one. This uses the particulars of the filter, and the particulars of the BST, to optimize. Having a first form be “handle an arbitrary tree” and then “optimize this if you know the tree is a BST”, that may be a nice interview sequence.

All BST questions are collected here; other binary-tree questions are here.

Binary Search Tree, Interview Questions

Range Sum of a BST (Leetcode 29)

Another one from the archives. This is a nice extension or sequel question to the core “find a value in a BST”, it stretches one’s experience with recursion (assuming that’s your approach). It may be a nice phone-screen question or similar.

The question pre-populates a solution, one that’s recursive but is inefficient. I don’t know how I feel about that, as presenting this. It sort of keeps it focused on what’s new about the problem, which I like, but it may also be distracting? I’ve seen people fixate on existing code and inadvertently box themselves in. (Edit: or maybe not? Maybe that was my existing code? Well, without accusing the question-author, this paragraph is a general question I’d like to consider.)

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None: return 0
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        return self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high) + root.val

What’s interesting to me is that it isn’t obvious how many iterations this would go through. I think that’d be an interesting question for someone who seems very adroit in reasoning about the runtime of other recursive algorithms.

Binary Tree, Interview Questions

Flatten Tree (Leetcode 7)

1 Comment

I think this question has a lot of potential. It is very algorithmic-y, but also has an idea that can come up in practice. Flattening a 2D object like a tree into a 1D object like a list happens in, e.g., the unit utility ls or the Window’s equivalent dir. However, the idea of keeping that same object in memory, and “punning” the linked-list structure over the tree structure, seems unneeded. Saving memory is great and I think we’re much too inclined to think memory is “free”, but from an pedagogical perspective we’re building off of a number of concepts.

Prerequisites and Solving

Of course the student should be very comfortable with typical recursion-and-binary-trees material. They should also be comfortable with updating pointers, like with complicated linked-lists questions (say, my favorite question of merging two linked lists).

Once we have all that, considering the question-actual: The “child management” is a bit tree-specific, but I think that’s OK (we’re allowed to talk about trees sometime). The idea of transforming the tree in question I think helps illustrate the power of recursion — many of the questions I’ve been thinking of don’t mutate the input.

One complication that caught me: You really have to account for both children, even the one you want to leave empty. I think this is a good “tough” question. I guess Leetcode calls it medium, sure. I’ve collected all my tree solutions here.

class Solution(object):
    def flatten(self, root):
        if root is None:
            return None
        root.right = self.flatten(root.right)
        if root.left is None:
            return root
        
        flatLeft = self.flatten(root.left)
        root.left = None
        t = flatLeft
        while t.right is not None: t = t.right
        t.right = root.right
        
        root.right = flatLeft
        return root
Binary Tree, Interview Questions

Depth of Binary Tree (Leetcode 6)

Leave a comment

I’m pretty sure I got this as a test question in “CS 102”, my data structures and algorithms course. The depth (or the height) of a tree. I really like phrasing this as the height of the tree, to be honest. My solution, as you see below, involves “adding 1” to the children’s depth. Especially if this is used as a teaching exercise, focusing on height helps avoid unneeded difficulties.

When we go over it in review sessions I’ve found students are often confused by the definition of the problem itself. It invites off-by-one errors, and also depth-versus-height. Especially when we say “now add one to the depth” — well, why are we increasing the depth as we go up the tree? It may be clear after-the-fact, but that can even detract from the satisfaction of solving it. If you can get them past that (or cleverly avoid them having to consider that aspect at all) it’s a great exercise.

Oh, and in this particular problem description, the math-y definition invites a certain implementation (ah, trace paths through the tree, very explicitly!). I think that’s a valuable thing to consider, the idea that a mechanical definition may very well different substantively from the “real” implementation, but I would rather introduce that idea outside the context of an interview or academic question. More like lecture material.

class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0
        leftDepth = self.maxDepth(root.left)
        rightDepth = self.maxDepth(root.right)
        maxChild = max(leftDepth, rightDepth)
        return maxChild + 1

More binary tree material can be found here.

Binary Tree, Interview Questions

Symmetric Tree (Leetcode 4)

Leave a comment

Is a binary tree symmetric about its root? How might one determine this?

There is a whole menagerie of binary-tree-questions that all reflect the same pattern of recursive thinking. I have a whole list here. Presented as a battery, it’s a nice way to build up recursive thinking muscles. Presented in isolation, it feels like an unpleasant surprise to do this sort of unusual problem-solving. Here’s the reasoning

  1. We do the base case.
  2. We imagine we have the answer for our smaller problems.
  3. We recombine those answers into our main answer.

The extra “half-step” here is that we need to realize that we want to be asking if our 2 children are symmetric. So while our initial input takes a single root, we’ll want to defer to an implementation of something like isMirror(root.left, root.right), which asks if the first parameter is a tree that is a mirror-image of the right. This is sort of a reduction: the tree root is symmetric if the two subtrees root.left and root.right are mirror-images of each other.

So, let’s use the 3 steps to implement isMirror(a, b), where a and b are two trees.

Applying the Skeleton

  1. Base cases: if they’re both empty (None or null or whatever), they’re mirror images. Return true, done! If only one is empty, they can’t be mirrors. Return false, done! If a and b have different root values, well then they’re not mirrors, so return false done! (That last case may be the most subtle. I can’t explain it better in this blog-post format).
  2. So far, at the “root” level, our two trees seem like mirror-images. Great. What we want now is a.left to be a mirror of b.right. (Note the left-versus right!) and a.right to be a mirror of b.left. We pretend we already have the answers.
  3. So if both those cases are true, our original trees are mirrors of each other. We’re done, return true! (Or false, if either of those recursive calls were false).

This question seems like a much-more-complicated version of tree equality. One might be (as I was) suspicious of whether the comparison in step 2 is exactly correct. It may be a sort of parity problem, where you only want to “flip” the left-versus-right comparison, and doing it on the 2nd or 3rd recursive layer will erroneously undo the mirroring. As it happens, this is simply not the case, but I think it’s very forgivable to act hesitantly in light of that concern.

def isMirror(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    if a.val != b.val:
        return False
    return isMirror(a.left, b.right) and isMirror(a.right, b.left)
class Solution(object):
    def isSymmetric(self, root):
        if root is None: return True
        return isMirror(root.left, root.right)