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

4 Responses to “Balanced Binary Search Trees”

  1. Jussi Piitulainen said

    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
    
  2. [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)))))))
    
  3. Jussi Piitulainen said

    Python functions need to have return statements. They return None by default.

  4. […] a recent exercise we wrote a program to determine if a binary tree was balanced. Today’s exercise is […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: