We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Trees: Is This a Binary Search Tree?
  5. Discussions

Trees: Is This a Binary Search Tree?

  • svdubl + 0 comments

    thank you! I started with the same elegant code as yours but before I figured out that you can pass by reference with the list I had to change it to this bulky code:

    def inOrderTraversalCheck(node, inValue=None):
	result = True
	if node.left is not None:
		(result, value) = inOrderTraversalCheck(node.left,min(node.data,inValue))
		if result is False:
			return (False, value)
		if value >= node.data:
			return (False, value)
	if node.right is not None:
		(result, value) = inOrderTraversalCheck(node.right, max(node.data,inValue))
		if result is False:
			return (False, value)
		if value <= node.data:
			return (False, value)
	if inValue is not None:
		if inValue >= node.data:
			return (False, node.data)
	if node.right or node.left is not None:
		return (True, max(node.data,value))
	else:
		return (True,node.data)


def checkBST(root):
	(result, value) = inOrderTraversalCheck (root)
	return (result)