## 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.

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() {
}

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