Binary Search Tree Checker – Practice Questions for the Facebook Interview – Queslers

Get Practice Questions for the Facebook Interview

Facebook’s coding interviews are hard, but not impossible. Like anything else, it just takes practice. We’ll walk you through it, step by step.

Binary Search Tree Checker

Write a function to check that a binary tree ↴ is a valid binary search tree. ↴

Here’s a sample binary tree node class:

  class BinaryTreeNode(object):
    def __init__(self, value):
        self.value = value
        self.left  = None
        self.right = None

    def insert_left(self, value):
        self.left = BinaryTreeNode(value)
        return self.left

    def insert_right(self, value):
        self.right = BinaryTreeNode(value)
        return self.right
Gotchas:

Consider this example:

A binary tree. To the left of the root is a subtree with a node containing 30, its left child containing 20, and its right child (highlighted in blue) 60.

Notice that when you check the blue node against its parent, it seems correct. However, it’s greater than the root, so it should be in the root’s right subtree. So we see that checking a node against its parent isn’t sufficient to prove that it’s in the correct spot.

We can do this in O(n) time and O(n) additional space, where n is the number of nodes in our tree. Our additional space is O(lgn) if our tree is balanced.

Breakdown:

One way to break the problem down is to come up with a way to confirm that a single node is in a valid place relative to its ancestors. Then if every node passes this test, our whole tree is a valid BST.

What makes a given node “correct” relative to its ancestors in a BST? Two things:

  • if a node is in the ancestor’s left subtree, then it must be less than the ancestor, and
  • if a node is in the ancestor’s right subtree, then it must be greater than the ancestor.

So we could do a walk through our binary tree, keeping track of the ancestors for each node and whether the node should be greater than or less than each of them. If each of these greater-than or less-than relationships holds true for each node, our BST is valid.

The simplest ways to traverse the tree are depth-first ↴ and breadth-first. ↴ They have the same time cost (they each visit each node once). Depth-first traversal of a tree uses memory proportional to the depth of the tree, while breadth-first traversal uses memory proportional to the breadth of the tree (how many nodes there are on the “level” that has the most nodes).

Because the tree’s breadth can as much as double each time it gets one level deeper, depth-first traversal is likely to be more space-efficient than breadth-first traversal, though they are strictly both O(n) additional space in the worst case. The space savings are obvious if we know our binary tree is balanced—its depth will be O(lgn) and its breadth will be O(n).

But we’re not just storing the nodes themselves in memory, we’re also storing the value from each ancestor and whether it should be less than or greater than the given node. Each node has O(n) ancestors O(lgn) for a balanced binary tree), so that gives us O(n^2) additional memory cost O(nlgn) for a balanced binary tree). We can do better.

Let’s look at the inequalities we’d need to store for a given node:

A binary tree with a root node of 50. To the left of the root is a node containing 30, whose left child contains 20, whose left child (highlighted in blue) contains 10.

Notice that we would end up testing that the blue node is <20, <30, and <50. Of course, <30 and <50 are implied by <20. So instead of storing each ancestor, we can just keep track of a lower_bound and upper_bound that our node’s value must fit inside.

Solution:

We do a depth-first walk through the tree, testing each node for validity as we go. If a node appears in the left subtree of an ancestor, it must be less than that ancestor. If a node appears in the right subtree of an ancestor, it must be greater than that ancestor.

Instead of keeping track of every ancestor to check these inequalities, we just check the largest number it must be greater than (its lower_bound) and the smallest number it must be less than (its upper_bound).

  def is_binary_search_tree(root):    # Start at the root, with an arbitrarily low lower bound
    # and an arbitrarily high upper bound
    node_and_bounds_stack = [(root, -float('inf'), float('inf'))]

    # Depth-first traversal
    while len(node_and_bounds_stack):
        node, lower_bound, upper_bound = node_and_bounds_stack.pop()

        # If this node is invalid, we return false right away
        if (node.value <= lower_bound) or (node.value >= upper_bound):
            return False

        if node.left:
            # This node must be less than the current node
            node_and_bounds_stack.append((node.left, lower_bound, node.value))
        if node.right:
            # This node must be greater than the current node
            node_and_bounds_stack.append((node.right, node.value, upper_bound))

    # If none of the nodes were invalid, return true
    # (at this point we have checked all nodes)
    return True

Instead of allocating a stack ↴ ourselves, we could write a recursive function that uses the call stack. ↴ This would work, but it would be vulnerable to stack overflow. However, the code does end up quite a bit cleaner:

  def is_binary_search_tree(root,                          lower_bound=-float('inf'),
                          upper_bound=float('inf')):
    if not root:
        return True

    if (root.value >= upper_bound or root.value <= lower_bound):
        return False

    return (is_binary_search_tree(root.left, lower_bound, root.value)
            and is_binary_search_tree(root.right, root.value, upper_bound))

Checking if an in-order traversal of the tree is sorted is a great answer too, especially if you’re able to implement it without storing a full list of nodes.

Complexity:

O(n) time and O(n) space.

The time cost is easy: for valid binary search trees, we’ll have to check all n nodes.

Space is a little more complicated. Because we’re doing a depth first search, node_and_bounds_stack will hold at most d nodes where d is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is O(d).

But we can also relate d to n. In a balanced tree, d is log2​n. And the more unbalanced the tree gets, the closer d gets to n.

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to the stack at each step. When the traversal hits the rightmost node, the stack will hold half of the n total nodes in the tree. Half n is O(n), so our worst case space cost is O(n).

Bonus:

What if the input tree has duplicate values?

What if -float(‘inf’) or float(‘inf’) appear in the input tree?

What We Learned:

We could think of this as a greedy ↴ approach. We start off by trying to solve the problem in just one walk through the tree. So we ask ourselves what values we need to track in order to do that. Which leads us to our stack that tracks upper and lower bounds.

We could also think of this as a sort of “divide and conquer” approach. The idea in general behind divide and conquer is to break the problem down into two or more subproblems, solve them, and then use that solution to solve the original problem.

In this case, we’re dividing the problem into subproblems by saying, “This tree is a valid binary search tree if the left subtree is valid and the right subtree is valid.” This is more apparent in the recursive formulation of the answer above.

Of course, it’s just fine that our approach could be thought of as greedy or could be thought of as divide and conquer. It can be both. The point here isn’t to create strict categorizations so we can debate whether or not something “counts” as divide and conquer.

Instead, the point is to recognize the underlying patterns behind algorithms, so we can get better at thinking through problems.

Sometimes we’ll have to kinda smoosh together two or more different patterns to get our answer.

Practice Questions for the Facebook Interview Review:

In our experience, we suggest you solve this Practice Questions for the Facebook Interview and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Practice Questions for the Facebook Interview

Find on Interview Cake

Conclusion:

I hope this Practice Questions for the Facebook Interview would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.