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

Untested, of course. I’m trying to simulate my being in the situation of that engineer :(

[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:

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.

Output: