Category Archives: Binary Tree

Binary Tree, Interview Questions, Recursion

Longest Univalue Path (Leetcode)

This leetcode question is interesting. It is from my archives. Originally, I misunderstood and thought you could only look for paths going “down”, but obviously as illustrated the question also admits “sideways” paths, see the second example.

Curiously, I was able to adapt my solution for the simpler interpretation and extend it to work for the more complicated interpretation too! Here is the code:

class Solution(object):
    def bottomUpBuilder(self, root):
        if root is None: return
        
        self.bottomUpBuilder(root.left)
        self.bottomUpBuilder(root.right)
        
        # can we continue a path from either of our children?
        self.longestPath[root] = 0
        if root.left and root.left.val == root.val:
            lval = self.longestPath[root.left]+1
            self.longestPath[root] = lval
        if root.right and root.right.val == root.val:
            rval = self.longestPath[root.right]+1
            self.longestPath[root] = max(self.longestPath[root], rval)
            
        # Can we join a path between our two children?
        # Note, crucially, that we're using "longestPath" for our child values;
        # we can't use asJoin because that would suggest a degree-3 node in our "path".
        self.asJoin[root] = 0
        if root.left and root.right and root.left.val == root.val and root.right.val == root.val:
            self.asJoin[root] = self.longestPath[root.left] + self.longestPath[root.right] + 2
    def longestUnivaluePath(self, root):
        self.longestPath = {}
        self.asJoin = {}
        self.bottomUpBuilder(root)
        m = 0
        for r in self.asJoin:
            m = max(m, self.asJoin[r])
        for r in self.longestPath:
            m = max(m, self.longestPath[r])
        return m

Discussion

You can see that there are basically 2 maps built, not just one. The asJoin map handles the case I forgot about.

So I can see this question as a nice one-two sort of question: first solve my simpler case, and then “can you extend that to the sideways case”? Well, the key insight that allows us to extend our code is hinted at in the comments: the asJoin map is defined in terms of longestPath, we don’t want to define it recursively.

This has a nice bottom-up iteration, and some neat invariants and applications. This question, on Leetcode, also has a certified solution. What is that solution? Let’s see.

Leetcode Solution Discussion

OK, it’s a more elegant recursive formulation (maybe?), and doesn’t admit my “extension” idea. Understanding why it’s linear-time is an interesting exercise.

More trees here, more recursion here.

Binary Tree, Interview Questions

Zigzag Order Traversal (Leetcode)

Long ago my students wanted binary tree problems, so I did a lot. I don’t think this one made the cut. This is from the archives, and according to my notes it took me a while to figure out the right iteration “pattern”. I think this stateful kind of iteration (the state is to help track the zigzag) is useful, though obviously here it’s contrived, so I think this is a good practice problem.

Approach

The key observation, and maybe this is too obvious, is that we can do BFS and keep track of the parity of what layer we’re in. If we’re in a left-to-right layer, we append our next children (who comprise the following layer) right-to-left, and vice-versa.

Realizing this in code, at least for me, was nontrivial. Here it is!

class Solution(object):
    def zigzagLevelOrder(self, root):
        if root is None:
            return []
        res = []
        currLevel = [root]
        reverse = False
        while currLevel:
            layer = []
            nextLevel = []
            # Drain the current level
            while currLevel:
                n = currLevel.pop()
                layer.append(n.val)
                if not reverse:
                    if n.left is not None:
                        nextLevel.append(n.left)
                    if n.right is not None:
                        nextLevel.append(n.right)
                else:
                    if n.right is not None:
                        nextLevel.append(n.right)
                    if n.left is not None:
                        nextLevel.append(n.left)
            res.append(layer[:])
            layer = []
            currLevel = nextLevel
            reverse = not reverse
        return res

Observations

Some thoughts:

  1. As we’re updating our state, this has some nice exercises with variable lifetime stuff. You can see I append a copy of layer, rather than a reference to it. I am not 100% clear on how references and scoping work in Python, so I went conservative. Turning that around, this exercise helped “poke at” my understanding of references and scoping.
  2. There’s something interesting going on about how the zig-zag-edness comes about implicitly from the tree structure and our iteration order.

Anyways. A weird tree question! More tree questions here.

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 Tree, Interview Questions

Tree Equality (Leetcode 15)

1 Comment

Now this I’m certain is a classic. I like how it’s not, well, a single tree! A neat second-lecture problem on binary trees, I’d think.

class Solution(object):
    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        if not self.isSameTree(p.left, q.left):
            return False
        if not self.isSameTree(p.right, q.right):
            return False
        return True

This “design” or style of programming is curious. Would the students suspect that “I thought about enough cases, and figured if there’s no other reason, we can return true”? I guess reasoning by cases never felt very persuasive to me when I was starting out, it’s hard to convey that we really have covered all the cases. I don’t know what threshold I crossed to feel more confident about reasoning-by-cases. Now that I do feel comfortable, I think this can be a valuable real-world tool, too.

Other binary tree problems with solutions can be found here.

Postscript: About 9 months after posting this, I was adding more questions, and I had misread my notes and thought this wasn’t a question I solved yet. My new approach is almost character-for-character the exact as listed above! Surprising.

Binary Tree, Interview Questions

Min Depth of Binary Tree (Leetcode 14)

Leave a comment

This one is interesting. It tricked me, I had answered the wrong question at first! It is curious how it defines the depth, that it requires a leaf node. I was computing something else, something like max height.

This one’s interesting because it provides a somewhat (unless if I’m missing something) complicated inductive case. Good to know!

class Solution(object):
    def minDepth(self, root):
        if root is None:
            return 0
        lDepth = self.minDepth(root.left)
        rDepth = self.minDepth(root.right)
        # Were we a leaf?
        if lDepth is 0 and rDepth is 0:
            return 1
        if lDepth is 0:
            return rDepth + 1
        if rDepth is 0:
            return lDepth + 1
        return min(lDepth, rDepth) + 1
Binary Tree, Interview Questions

Univalued Binary Tree (Leetcode 13)

Leave a comment

I think I want to do a battery of tree exercises. Here’s one. The names some of these community-contributed questions come up with are quite striking.

We can either think about maintaining some global, “ah, here is the value we should compare again”, or we can exploit the transitive nature of equality.

class Solution(object):
    def isUnivalTree(self, root):
        if root is None: return True
        if root.left is not None and root.left.val != root.val:
            return False
        if root.right is not None and root.right.val != root.val:
            return False
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Hey, let’s do the global approach too, why not. Well, not global exactly, but you know.

class Solution(object):
    def isUnivalTreeInternal(self, root):
        if root is None: return True
        if root.val != self.val: return False
        return self.isUnivalTreeInternal(root.left) and self.isUnivalTreeInternal(root.right)
    def isUnivalTree(self, root):
        if root is None: return True
        self.val = root.val
        return self.isUnivalTreeInternal(root)
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)