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.
Programming Praxis 
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 […]
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++”]
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