CareerCup4.5.cpp

CareerCup4.5.cpp

/*
 Chapter 4
 
 4.5  Implement a function to check if a binary tree is a binary search tree.
 
 */

#include <iostream>
#include <stack>

using namespace std;

// Define tree_node struct
typedef struct tree_node {
    int value;
    struct tree_node* left;
    struct tree_node* right;
    tree_node(int value);
} tree_node;
// Constructor
tree_node::tree_node(int value) {
    this->value = value;
    left = NULL;
    right = NULL;
}

bool isBST(tree_node root)
{
    tree_node* cur = &root;
    stack<tree_node> s;
    int ref = 0;
    // set ref value as the leftest node's value
    while (cur) {
        ref = cur->value;
        cur = cur->left;
    }
    // reset cur
    cur = &root;
    // inorder traverse and compare
    while (!s.empty() || cur) {
        // push visited node and go to leftest node
        if (cur) {
            s.push(*cur);
            cur = cur->left;
        }
        else {
            cur = &s.top();
            if (s.top().value < ref)
                return false;
            ref = cur->value;
            s.pop();
            cur = cur->right;
        }
    }
    return true;
}


// Main Function to test
int main()
{
    // Initialize a binary tree
    /*     4
         /  \
       2     16
      /  \   /  \
     0   3  11   100   */
    tree_node root(4);
    tree_node l(2);
    tree_node ll(0);
    tree_node lr(3);
    tree_node r(16);
    tree_node rl(11);
    tree_node rr(100);
    root.left = &l;
    root.right = &r;
    root.left->left = &ll; root.left->right = &lr;
    root.right->left = &rl; root.right->right = &rr;
    if (isBST(root))
        cout << "Yes. It's a BST." << endl;
    else
        cout << "No. Not a BST." << endl;
    return 0;
}