Tag Archives: recursion

Binary Search Tree, Interview Questions

Minimum Distance Between BST Nodes (Leetcode)

This is a fun-enough question, I guess. I feel like I’ve seen a few questions with BSTs where the answer involves the idea that in-order traversal presents their content as a sorted list. Or should… Oh yeah, this would much-improve my answer for this older question.

Interlude: Yield Statements

I guess sometimes they’re called coroutines? Fun excuse to use those in Python. For our purposes they’re a “better” (?) way of collapsing the BST we have into a sorted list. The magic of that isn’t the coroutines of course, it’s that in-order traversal of a BST presents the contents as a sorted list. The yield statement just makes it nice, we don’t have to allocate a whole intermediate list.

Solution

class Solution(object):
    def inOrderYield(self, root):
        if root is None:
            return
        for x in self.inOrderYield(root.left):
            yield x
        yield root.val
        for y in self.inOrderYield(root.right):
            yield y
    def minDiffInBST(self, root):
        minDiff = None
        prev = None
        for v in self.inOrderYield(root):
            if prev is None:
                prev = v
                continue
            if minDiff is None:
                minDiff = v - prev
                prev = v
                continue
            minDiff = min(minDiff, v - prev)
            prev = v
        return minDiff

I bet there’s a better way of doing the final loop in our main function.

More BST goodness 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.

Interview Questions, Linked List

Flatten a Doubly-Linked List (Leetcode 8)

Leave a comment

Isn’t this basically the same as the last one? Instead of left and right it’s “child” and “next”. The doubly-linked stitching is a bit different, but nothing major. Interesting contrast.

class Solution(object):
    def flatten(self, head):
        if head is None:
            return None
        if head.child is None:
            self.flatten(head.next)
            return head
        flatChild = self.flatten(head.child)
        head.child = None

        childEnd = flatChild
        while childEnd.next != None:
            childEnd = childEnd.next
        
        
        oldNext = head.next
        if oldNext:
            oldNext.prev = childEnd
        childEnd.next = oldNext

        flatChild.prev = head
        head.next = flatChild
        
        return head
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)
Interview Questions, Recursion

Tribonacci (Code Wars 4)

1 Comment

Let’s compute the complete Tribonacci (riff off of “Fibonacci”) sequence.

It’s worth a few minutes understanding and “visualizing” what the solution might look like. In this case, I just mean that we’re going to be returning a list. Moreover, (most of) the elements in that list are computed by prior elements in that list. The list is going to be n elements long (the same n as is a parameter to our function).

One of my favorite exercises: dealing with the edge/easy cases.

  1. If n is 0, we can return the empty list.
  2. If n is less than or equal to the number of elements in signature, we can just return that appropriate subsequence.
  3. Otherwise, we already have enough elements in signature to compute all the other elements we need.

And that’s the answer:

def tribonacci(signature, n):
    if n == 0:
        return []
    if n <= len(signature):
        return signature[:n]
    result = signature[:]
    for i in range(3, n):
        s = result[i-1]+result[i-2]+result[i-3]
        result.append(s)
    return result

Additional Thoughts

  1. The slice on line 5 may not be available in all languages; it will just be more verbose, if slicing isn’t available, with the spirit being the same.
  2. I think sometimes we’re returning a shallow copy (line 5), otherwise a deep copy. Probably not ideal. I wouldn’t let this pass code-review.
  3. We often have for loops that go over an array of length n. Here we’re creating an array of length n. That’s a fun contrast.
  4. This sort of algorithm, where we build the contents of the list based off of previous elements, hasn’t come up very often in my professional experiences. I suppose it’s neat to see what that kind of code looks like, though I think it doesn’t add much versus other, more applicable loop questions.

I’d categorize this question as one in the “recursion” topic. You can find all such questions on this site here.