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

6 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++”]

  6. Daniel said

    Here’s a solution in Java. It uses pre-order traversal, and it each node checks that the heights of the left sub-tree and right sub-tree are within 1. The height calculation uses memoization to avoid redundant calculations.

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    
    public class BinarySearchTree<T extends Comparable<T>> {
        class Node {
            T value;
            Node left;
            Node right;
    
            Node(T value) {
                this.value = value;
            }
        }
    
        Node root;
    
        private Node insert(Node node, Node root) {
            if (root == null) return node;
            int compare = node.value.compareTo(root.value);
            if (compare <= 0) {
                root.left = insert(node, root.left);
            } else {
                root.right = insert(node, root.right);
            }
            return root;
        }
    
        Node insert(T value) {
            Node node = new Node(value);
            root = insert(node, root);
            return node;
        }
    
        int height(Node n, Map<Node, Integer> cache) {
            if (cache.containsKey(n)) {
                return cache.get(n);
            }
            int height = 0;
            if (n != null) {
                int leftHeight = height(n.left, cache);
                int rightHeight = height(n.right, cache);
                height = Math.max(leftHeight, rightHeight) + 1;
            }
            cache.put(n, height);
            return height;
        }
    
        boolean balanced() {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            Map<Node, Integer> heightCache = new HashMap<>();
            while (!stack.empty()) {
                Node node = stack.pop();
                if (node == null) {
                    continue;
                }
                int leftHeight = height(node.left, heightCache);
                int rightHeight = height(node.right, heightCache);
                if (Math.abs(rightHeight - leftHeight) > 1) {
                    return false;
                }
                stack.push(node.right);
                stack.push(node.left);
            }
            return true;
        }
    
        public String toString(String prefix, Node node, boolean right) {
            if (node == null) return "";
            StringBuffer sb = new StringBuffer();
            sb.append(toString(prefix + (right ? "    " : "│   "), node.right, true));
            sb.append(prefix + (right ? "┌── " : "└── ") + node.value + "\n");
            sb.append(toString(prefix + (right ? "│   " : "    "), node.left, false));
            return sb.toString();
        }
    
        public String toString() {
            return toString("", root, false);
        }
    
        public static void main(String[] args) {
            BinarySearchTree<Integer> bst = new BinarySearchTree<>();
            int[] values1 = {43,2,5,42,-3,672};
            for (int i = 0; i < values1.length; ++i) {
                bst.insert(values1[i]);
            }
            System.out.println("Original");
            System.out.print(bst);
            System.out.format("Balanced: %s\n", bst.balanced());
    
    
            int[] values2 = {0,120,105,845,881};
            for (int i = 0; i < values2.length; ++i) {
                bst.insert(values2[i]);
            }
            System.out.println();
            System.out.println("Modified");
            System.out.print(bst);
            System.out.format("Balanced: %s\n", bst.balanced());
        }
    }
    

    Output:

    Original
    │   ┌── 672
    └── 43
        │       ┌── 42
        │   ┌── 5
        └── 2
            └── -3
    Balanced: false
    
    Modified
    │           ┌── 881
    │       ┌── 845
    │   ┌── 672
    │   │   └── 120
    │   │       └── 105
    └── 43
        │       ┌── 42
        │   ┌── 5
        └── 2
            │   ┌── 0
            └── -3
    Balanced: true
    

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: