## Sunday, November 27, 2016

### HackerRank - Is This a Binary Search Tree?

Problem:

Solution:

To test if a given tree is a binary search tree, we simply do an in-order traversal and test if the value comes in order.

Slightly annoyed by the fact that the author re-defined binary search tree to not have duplicated values.

Analysis:

Suppose there exists an algorithm that solve the problem without reading all the nodes, an adversary can choose to give that node a value that doesn't fit the requirement of a binary search tree, therefore we need at least linear time, showing our algorithm is asymptotically optimal.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/is-binary-search-tree

#include "HACKER_RANK_IS_BINARY_SEARCH_TREE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_IS_BINARY_SEARCH_TREE
{
struct Node
{
int data;
Node* left;
Node* right;
};

bool has_last = false;
int last = 10086;

bool checkBST(Node* root)
{
if (root == nullptr)
{
return true;
}
if (!checkBST(root->left)) { return false; }
if (has_last)
{
if (root->data < last)
{
return false;
}
}
else
{
has_last = true;
}
last = root->data;
if (!checkBST(root->right)) { return false; }
return true;
}
};

using namespace _HACKER_RANK_IS_BINARY_SEARCH_TREE;

int HACKER_RANK_IS_BINARY_SEARCH_TREE()
{
Node a;
Node b;
Node c;
Node d;
Node e;
Node f;
a.data = 3;
b.data = 5;
c.data = 2;
d.data = 1;
e.data = 4;
f.data = 6;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = nullptr;
cout << checkBST(&a) << endl;
return 0;
}