## Balanced Binary Search Trees

### March 3, 2017

We begin with the same binary search tree code we wrote in a recent exercise:

```(define (insert lt? x tree)
(cond ((null? tree)
(list x (list) (list)))
((lt? x (car tree))
((lt? (car tree) x)
(else tree)))```
```(define (member? lt? x tree)
(cond ((null? tree) #f)
((lt? x (car tree)) (member? lt? x (cadr tree)))
((lt? (car tree) x) (member? lt? x (caddr tree)))
(else #t)))```

A binary search tree is balanced if the depths of its two children are the same, and if both of its two children are balanced. We are assuming here perfect balance, so that only trees with 2n−1 nodes for integer n can possibly be balanced:

```(define (depth tree)
(if (null? tree) 0
(+ 1 (max (depth (cadr tree))
```(define (balanced? tree)
(if (null? tree) #t

Here are two examples:

```> (balanced? (insert < 4 (insert < 6 (insert < 0 (insert < 7
(insert < 1 (insert < 5 (insert < 2 (insert < 3 (list))))))))))
#f
> (balanced? (insert < 0 (insert < 6 (insert < 4 (insert < 2
(insert < 1 (insert < 5 (insert < 3 (list)))))))))
#t```

There’s a lot of extra work going on there. Both functions use the same recursion, so they could be flattened into a single function. And both functions recompute previously-computed depths in their recursive calls; a more clever function could order its computations to calculate the depths only once. An even more clever function never even computes the depth: a tree is balanced if it is null, or if both its children are null, or if both its children are non-null and are balanced:

```(define (balanced? tree)
(or (null? tree)

Here are the same two examples:

```> (balanced? (insert < 4 (insert < 6 (insert < 0 (insert < 7
(insert < 1 (insert < 5 (insert < 2 (insert < 3 (list))))))))))
#f
> (balanced? (insert < 0 (insert < 6 (insert < 4 (insert < 2
(insert < 1 (insert < 5 (insert < 3 (list)))))))))
#t```

You can run the program at http://ideone.com/JFq9dE. I wonder if CBP agents speak Scheme?

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
def right(node):
node

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
```