Category Archives: Binary Search 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 Search Tree, Recursion

Validate Binary Search Tree (Leetcode 36)

1 Comment

This “medium” problem does present a nice way where an initial solution (i.e., mine) has lots of room for improvement. Assuming the student knows what a binary search tree is and is fairly comfortable with them, and recursion, this is an excellent homework problem. In a sense, it’s taking the invariants of a binary search tree, and taking them a step further and applying them to solve a new problem, validation. While this is a bit contrived, I think validation for a datastructure has good-enough motivation.

The solution code is a bit bigger than typical, and I bet it can be made a lot smaller and more efficient. I just was confident this would work, so I went that way. An opportunity, later, to discuss how to improve code after-the-fact?

Solution Ideas

  1. All nodes to the left of our “root” (and remember we’re going to look at every node as its own root) should be smaller than us. So we’d like to know what the largest value to our left is—if we’re bigger than that, then we’re OK. Similarly, we want to know the smallest value to our right [Note: terrifyingly, as I was writing this, the “we want to know the smallest value to…” auto-complete filled in “to our right”! I suppose it saw the opposites of larger and smallest, and mapped that to right/left? Spooky!].
  2. So I imagined as if I knew the min-and-max values for each node. If we had that attached to each node, we can simply query our immediate children and see what they each have as their min/max values. If our value is smaller than the max of our left, or larger than the min of our right, we are not a valid BST.
  3. Additionally, if we have the min/max values of our children, we can easily compute the min/max values of ourselves.

Finding the min or max value of a tree is an easy-enough recursive exercise. Doing both at the same time is a nice sequel. Doing it for all node is itself an interesting problem: I haven’t done out the arithmetic, but the temptation to do it “purely recursively” would lead to a very expensive algorithm. I don’t know if it’s quadratic per-se, but it sounds like “for each node, walk the tree”. So you want a very deliberate bottom-up approach.

Conclusion

My solution is a bit of a hybrid where I set the stage for a two-pass approach, computing global maps for the nodes, but then realized I could determine a BST violation while computing the maps. I bet we can get rid of the maps and turn this into a more typical recursive formulation. Later!

class Solution:
    def solution(self, root):
        if root is None:
            self.minMap[root] = None
            self.maxMap[root] = None
            return True
        
        l = self.solution(root.left)
        if not l: return False # might as well stop
        
        r = self.solution(root.right)
        if not r: return False
        
        lm = self.maxMap[root.left]
        if lm is not None and lm >= root.val:
            return False
        
        rm = self.minMap[root.right]
        if rm is not None and rm <= root.val:
            return False
        
        rMax = self.maxMap[root.right]
        if rMax is None:
            rMax = root.val
        lMin = self.minMap[root.left]
        if lMin is None:
            lMin = root.val
        
        self.maxMap[root] = rMax
        self.minMap[root] = lMin
        
        return True
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # Observation: if we check each node, we'll be doing something that feels
        # a little bit too "quadratic" (for each node, validate the rest of the tree)
        # What we can do is build a map of nodes to min/max values under that tree,
        # and then do another pass (in parallel?) to do the final validation.
        # So, in other words:
        
        # Silly initializatio
        self.minMap = {}
        self.maxMap = {}
        return self.solution(root)

More BST questions can be found 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 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.