Tag Archives: binary tree

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

Merge Two Binary Trees (Leetcode 31)

Another from the archives. Part of a big battery where I went through a lot of tree problems, I guess. I wouldn’t call this problem a classic one (versus, say, Tree Equality), but I think it’s a nice “classroom” exercise on making sure someone feels fluent in tree-manipulation.

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # destructive operation
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        
        return root1

Discussion Points

  1. This follows the classic “skeleton” of solving binary tree problems with recursion. We handle (in the case, the 2) “base cases” of when the tree(s) are null; we solve the smaller cases, and we combine those results to synthesize the new tree.
  2. In this case we treat the operation as wholly destructive. When I help newer programmers, that’s a concept they are often unfamiliar with. Here we are unusually destroying both trees (I’m sure we can solve this without destructive operations; that’s a fun follow-up in many circumstances).
  3. I think that we reassign the left and right children of root1, and in general do some subtle interactions between subtrees, makes this a good next-level exercise. A lot harder than, say, incrementing all the values in a single tree by 1!

All solved tree exercises in this blog series can be found 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)