From: http://www.mitbbs.com/article_t/JobHunting/32877637.html

A B-tree is a generalization of a binary search tree, where each node has n
keys and n+1 children and n can be different for each node. The keys are
sorted the same as in a binary search tree. For each key k in the tree, all
children to the left must have keys less than k, and all children to the
right must have keys greater than k.

QUESTION:
Write a method that validates whether a B-tree is correctly sorted. You do
NOT need to validate whether
the tree is balanced. Use the following model for a node in the B-tree.
struct node {
  int* values;
  struct node** children;
};

Answer:

This is similar to validate a BST.

For a BST, validation is:

bool IsBST(TreeNode * root) {
    return IsValidBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
}
bool IsValidBST(TreeNode * root, long long mi, long long ma) {
    if (! root) return true;
    return root->val > mi && root->val < ma && 
           IsValidBST(root->left, mi, root->val) &&
           IsValidBST(root->right, root->val, ma);
}

So for a B-tree, validation is something like this:


#include <iostream>
using namespace std;

struct node {
  int* values;
  struct node** children;
};

bool IsValidBTree(struct node * root, long long mi, long long ma);

bool IsBTree(struct node * root) {
    return IsValidBTree(root, INT_MIN - 1ll, INT_MAX + 1ll);
}
bool IsValidBTree(struct node * root, long long mi, long long ma) {
    if (! root) return true;

    long long cur = mi;
    int * v = root->values;
    struct node ** c = root->children;

    while (*v != 0) {
        if (cur >= *v) return false; // check each value.
        if (! IsValidBTree(*c, cur, *v)) return false; // check child.
        cur = *v;
        ++ v, ++ c;
    }
    if (cur >= ma) return false; // check last value.
    ++ c;
    if (! IsValidBTree(*c, cur, ma)) return false; // check last child.

    return true;
}

int main() {
    return 0;
}