Info N Bites

Tech Interview: Implement a Function to Validate a Binary Search Tree

Write a function that takes a binary search tree node as input, and returns true if the input represents a valid binary search tree or false otherwise. 

Yes, this is an example of a technical interview question from top companies like Facebook, Google, etc. Do they always word it the same way, probably not, but we have spoken to candidates who encountered this exact same question. 

If you are preparing for a technical interview, try to implement the solution on your own, then take a look at our solution below. 

There are several things you must understand in order to solve this problem.

  1. What is a binary search tree?
  2. What determines where a node goes in a binary search tree: condition for going left or right. 

If you understand the above concepts, then solving a problem like this becomes easy. 

In a typical interview, make sure you ask all these clarifying questions, including what qualifies as a valid input: e.g. is a null input acceptable and should we just return false for that?

So what is a BST? To help you with this, just watch this video or google the terms ‘binary search tree tutorial’. 


Solution: Implement a Function to Validate a Binary Search Tree

def isValidBst(treeNode):
   # instantiate and empty stack
   stack = []

   while len(stack)>0:
      right_node,lower_bound,upper_bound = stack.pop(0)
      if right_node is None:
      val = right_node.value
      if val < lower_bound or val >= upper_bound:
         return False
      if right_node.left:
      if rn.right:

          return True


That is it. After you implement this, walk through some simple examples. We will leave it up to you to come up with examples and walk through some of them. 

Good luck in your quest for knowledge or quest for a software engineering job with Big Tech!


It's always been a love hate relationship not seeing sports and tech blended in a unique way. I came to change the narrative. Sports and fitness enthusiast, tech junkie and lover of the greater good, I am the Editor and Chief of Info N Bites.