Coding Interview Practice: Binary Search Trees

is_bst.cpp

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>

#include <cmath>
#include <climits>
#include <cassert>

#define FACTOR 1.5

//
// Lessons learned:
//
// - std::vector interface (push_back, pop_back, back -- pop_back returns void)
// - std::max needs #include <algorithm>
// - log needs include <cmath>
// - C++ has a bool type -- use it
// - result of calloc needs to be cast from (void *) to the appropriate pointer type
//

struct BinaryTreeNode
{
    int value;
    BinaryTreeNode *left;  // NULL if no left child
    BinaryTreeNode *right; // NULL if no right child
};

//
// Returns true if the specified binary tree is an auto-balancing 
// binary search tree.
//
// An auto-balancing binary search tree satisfies two invariants:
//
// 1) For all nodes, left_value < current_value < right_value
// 2) Height of tree must be proportional to log2(number_of_nodes)
//
bool
is_BST(BinaryTreeNode *root)
{
    int num_nodes = 0;
    int max_level = 0;
    int prev = INT_MIN;
    std::vector<BinaryTreeNode *> stack;
    std::map<BinaryTreeNode *, int> level;
    std::set<BinaryTreeNode *> visited;
    level[root] = 1;
    stack.push_back(root);
    // Perform an in-order traversal of the tree.  All the elements must be in
    // ascending order to satisfy the first invariant.  While traversing, keep
    // track of the longest branch (max_level).
    while (stack.size())
    {
        BinaryTreeNode *node = stack.back();
        // Traverse left subtree.
        if (node->left && visited.find(node->left) == visited.end())
        {
            stack.push_back(node->left);
            level[node->left] = level[node]+1;
            continue;
        }
        // Check ordering invariant
        if (node->value <= prev)
            return false;
        // Visit node
        stack.pop_back();
        visited.insert(node);
        prev = node->value;
        ++num_nodes;
        max_level = std::max(max_level, level[node]);
        // Traverse right subtree
        if (node->right)
        {
            level[node->right] = level[node]+1;
            stack.push_back(node->right);
        }
    }
    // Check height invariant
    return max_level < log2(num_nodes) * FACTOR;
}

BinaryTreeNode *
btn_new(int value) 
{
    BinaryTreeNode *node = (BinaryTreeNode *)calloc(sizeof(BinaryTreeNode), 1);
    assert(node);
    node->value = value;
    return node;
}

BinaryTreeNode *
example1()
{
    BinaryTreeNode *six = btn_new(6);
    BinaryTreeNode *three = btn_new(3);
    BinaryTreeNode *seven = btn_new(7);
    BinaryTreeNode *two = btn_new(2);
    BinaryTreeNode *fifty_nine = btn_new(59);
    six->left = three;
    three->left = two;
    three->right = fifty_nine;
    six->right = seven;
    return six;
}

BinaryTreeNode *
example2()
{
    BinaryTreeNode *fifty = btn_new(50);
    BinaryTreeNode *forty_seven = btn_new(47);
    BinaryTreeNode *fifty_seven = btn_new(57);
    BinaryTreeNode *thirty = btn_new(30);
    fifty->left = forty_seven;
    fifty->right = fifty_seven;
    fifty_seven->left = thirty;
    return fifty;
}

BinaryTreeNode *
example3()
{
    BinaryTreeNode *two = btn_new(2);
    BinaryTreeNode *one = btn_new(1);
    BinaryTreeNode *thousand = btn_new(1000);
    BinaryTreeNode *three = btn_new(3);
    two->left = one;
    one->right = thousand;
    two->right = three;
    return two;
}

BinaryTreeNode *
example4()
{
    BinaryTreeNode *five = btn_new(5);
    BinaryTreeNode *two = btn_new(2);
    BinaryTreeNode *six = btn_new(6);
    BinaryTreeNode *one = btn_new(1);
    BinaryTreeNode *three = btn_new(3);
    BinaryTreeNode *seven = btn_new(7);
    BinaryTreeNode *ten = btn_new(10);
    five->left = two;
    two->left = one;
    two->right = three;
    five->right = six;
    six->left = seven;
    six->right = ten;
    return two;
}

int
main(void)
{
    // The three examples from https://gist.github.com/7226177f2724572386c5
    std::cout << is_BST(example1()) << std::endl;
    std::cout << is_BST(example2()) << std::endl;
    std::cout << is_BST(example3()) << std::endl;
    // A properly-balanced BST
    std::cout << is_BST(example4()) << std::endl;
}

Makefile

CFLAGS=-ggdb -Wall

all: is_bst.out

# $< the dependencies
# $@ the target
is_bst.out: is_bst.o
	g++ -Wall -ggdb $< -o $@

clean:
	rm -rf *.out *.o

Thanks for submitting as always. You'll be in tomorrow's issue!