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?

  • eileen_duffner + 2 comments

    Can you explain how the single closure variable works? I tried to use a variable that I passed in to a helper function, but I'm assuming it was working they way I thought.

    • atb27 + 1 comment

      Actually that was a better approach. What he basically did was while comparing root->data with root->left data the last value will be set to root ->data and while the comparison is between root and its right child the last value will be the right child .Thus he made sure that a single comparison is enough for verifying the validity of the tree. A good one

      • witygass + 1 comment

        I agree, the purely functional approach is probably better in hindsight for any real life application. The solution passing the var down would have avoided possible external side effects where mine uses a global variable.

        • Fantoxicated + 0 comments

          I used the same approach, using the inorder traversal. But in my case I've used an instance of a class for storing the last value. Is it a good practise to do this?

          class staticVar:
    last = None

variable = staticVar()

def checkBST(root):
    if root != None:
        if not checkBST(root.left):
            return False

        if variable.last != None and variable.last.data >= root.data:
            return False

        variable.last = root
        return checkBST(root.right)
        
    return True
    • Dan_Golding + 1 comment

      I ended up with pretty much the same code but instead of a closure variable I just passed the variable in. I used a single element list since it's gets passed by reference which allows changes to persist when going back down the call stack:

      def checkBST(root):
    return(check_in_order(root,[-1]))
    
def check_in_order(root,prev):
    result = True
    if root.left is not None:
        result &= check_in_order(root.left,prev)
    if prev[0] >= root.data:
        return False
    prev[0] = root.data
    if root.right is not None:
        result &= check_in_order(root.right,prev)
    return result
      • 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)