MangaWrite 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.
- What is a binary search tree?
- 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 = []
stack.append((treeNode,float('-inf'),float('inf')))
while len(stack)>0:
right_node,lower_bound,upper_bound = stack.pop(0)
if right_node is None:
continue
val = right_node.value
if val < lower_bound or val >= upper_bound:
return False
if right_node.left:
stack.append((right_node.left,lower_bound,right_node.value))
if rn.right:
stack.append((right_node.right,right_node.value,upper_bound))
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!
