Balanced Binary Search Trees
March 3, 2017
The story exploded across the intertubes a few days ago: A software engineer trying to enter the United States on a work visa was asked to prove his occupation by writing a program for the Customs and Border Protection agent:
Write a function to check if a Binary Search Tree is balanced.
Let’s help him.
Your task is to write a function to check if a binary search tree is balanced. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Advertisements
Pages: 1 2
Untested, of course. I’m trying to simulate my being in the situation of that engineer :(
# assume: tree is None or left(tree), right(tree) are trees def dep(tree): '''Return the depth of the tree if it's balanced, None if it's not. ''' if tree is None: return 0 west = dep(left(tree)) if west is None: return None east = dep(right(tree)) if east is None: return None if -1 <= west - east <= 1: return 1 + max(west, east) return None def isbalanced(tree): return dep(tree) is not None[sourcelang=”css”]
def makeNode(left=None, right=None):
(left, right)
def left(node):
node[0]
def right(node):
node[1]
left = makeNode(left=makeNode(left=makeNode(left=makeNode(left=makeNode()))))
print(“{} is {}balanced.”.format(‘left’,”” if isbalanced(left) else “not “))
left is balanced.
# good job Python!
[/sourcelang=”css”]
In Common Lisp:
(defgeneric balancedp (tree) (:documentation "Return nil if the tree is not balanced, or its number of nodes if it is.") (:method ((node t)) 0) (:method ((node node)) (let ((lc (balancedp (node-left node))) (rc (balancedp (node-right node)))) (and lc rc (<= (abs (- lc rc)) 1) (+ 1 lc rc))))) (assert (balancedp nil)) (assert (balancedp (make-node))) (assert (balancedp (make-node :left (make-node)))) (assert (not (balancedp (make-node :left (make-node :right (make-node)))))) (assert (balancedp (make-node :left (make-node :right (make-node)) :right (make-node :left (make-node))))) (assert (not (balancedp (make-node :left (make-node :left (make-node) :right (make-node)) :right (make-node :left (make-node :left (make-node)))))))Python functions need to have return statements. They return None by default.
[…] a recent exercise we wrote a program to determine if a binary tree was balanced. Today’s exercise is […]