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

5 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 […]

  5. A C++ solution that checks for near perfect balance.
    [sourcelang=”c++”]

    struct Node
    {
    int key;
    Node * left, * right;

    Node(int k)
    {
    key = k;
    left = right = NULL;
    }
    };

    int height(Node * node)
    {
    if(node == NULL)
    return 0;

    return max( height(node->left), height(node->right));

    }

    bool IsBalanced(Node * node)
    {
    int diff = height(node->left) – height(node->right);
    return ( -1 <= diff && diff left) && IsBalanced(node->right));

    }

    [/sourcelang=”c++”]

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: