Is it a binary search tree?
Programming Assignment 4: Binary Search Trees
Problem Introduction
In this problem you are going to test whether a binary search tree data structure from some programming
language library was implemented correctly. There is already a program that plays with this data structure
by inserting, removing, searching integers in the data structure and outputs the state of the internal binary
tree after each operation. Now you need to test whether the given binary tree is indeed a correct binary
search tree. In other words, you want to ensure that you can search for integers in this binary tree using
binary search through the tree, and you will always get correct result: if the integer is in the tree, you will
find it, otherwise you will not.
Problem Description
Task. You are given a binary tree with integers as its keys. You need to test whether it is a correct binary
search tree. The definition of the binary search tree is the following: for any node of the tree, if its
key is 𝑥, then for any node in its left subtree its key must be strictly less than 𝑥, and for any node in
its right subtree its key must be strictly greater than 𝑥. In other words, smaller elements are to the
left, and bigger elements are to the right. You need to check whether the given binary tree structure
satisfies this condition. You are guaranteed that the input contains a valid binary tree. That is, it is a
tree, and each node has at most two children.
Input Format. The first line contains the number of vertices 𝑛. The vertices of the tree are numbered
from 0 to 𝑛 − 1. Vertex 0 is the root.
The next 𝑛 lines contain information about vertices 0, 1, ..., 𝑛−1 in order. Each of these lines contains
three integers 𝑘𝑒𝑦𝑖
, 𝑙𝑒𝑓 𝑡𝑖 and 𝑟𝑖𝑔𝑡𝑖 — 𝑘𝑒𝑦𝑖
is the key of the 𝑖-th vertex, 𝑙𝑒𝑓 𝑡𝑖
is the index of the left
child of the 𝑖-th vertex, and 𝑟𝑖𝑔𝑡𝑖
is the index of the right child of the 𝑖-th vertex. If 𝑖 doesn’t have
left or right child (or both), the corresponding 𝑙𝑒𝑓 𝑡𝑖 or 𝑟𝑖𝑔𝑡𝑖 (or both) will be equal to −1.
Constraints. 0 ≤ 𝑛 ≤ 105
; −2
31 < 𝑘𝑒𝑦𝑖 < 2
31 − 1; −1 ≤ 𝑙𝑒𝑓 𝑡𝑖
, 𝑟𝑖𝑔𝑡𝑖 ≤ 𝑛 − 1. It is guaranteed that the
input represents a valid binary tree. In particular, if 𝑙𝑒𝑓 𝑡𝑖 ̸= −1 and 𝑟𝑖𝑔𝑡𝑖 ̸= −1, then 𝑙𝑒𝑓 𝑡𝑖 ̸= 𝑟𝑖𝑔𝑡𝑖
.
Also, a vertex cannot be a child of two different vertices. Also, each vertex is a descendant of the root
vertex. All keys in the input will be different.
Output Format. If the given binary tree is a correct binary search tree (see the definition in the problem
description), output one word “CORRECT” (without quotes). Otherwise, output one word “INCORRECT” (without quotes).
Time Limits.
language C C++ Java Python C# Haskell JavaScript Ruby Scala
time (sec) 2 2 3 10 3 4 10 10 6
Memory Limit. 512MB.
Sample 1.
Input:
3
2 1 2
1 -1 -1
3 -1 -1
Output:
CORRECT
2
1 3
Left child of the root has key 1, right child of the root has key 3, root has key 2, so everything to the
left is smaller, everything to the right is bigger.
Sample 2.
Input:
3
1 1 2
2 -1 -1
3 -1 -1
Output:
INCORRECT
1
2 3
The left child of the root must have smaller key than the root.
Sample 3.
Input:
0
Output:
CORRECT
Empty tree is considered correct
Solution :
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
using std::cin;
struct Node {
int key;
int left;
int right;
Node() : key(0), left(-1), right(-1) {}
Node(int key_, int left_, int right_) : key(key_), left(left_), right(right_) {}
};
bool IsBst(const vector<Node>& tree, int ind, long min, long max) {
bool left = 1, right = 1;
if (tree[ind].key < min || tree[ind].key + 1 > max)
return 0;
if (tree[ind].left != -1)
left = IsBst(tree, tree[ind].left, min, tree[ind].key);
if (tree[ind].right != -1)
right = IsBst(tree, tree[ind].right, tree[ind].key, max);
return left && right;
}
bool IsBinarySearchTree(const vector<Node>& tree) {
long min = -2147483647 - 1;
long max = 2147483647;
if (!tree.empty())
if (!IsBst(tree, 0, min, max))
return false;
return true;
}
int main() {
int nodes;
cin >> nodes;
vector<Node> tree;
for (int i = 0; i < nodes; ++i) {
int key, left, right;
cin >> key >> left >> right;
tree.push_back(Node(key, left, right));
}
if (IsBinarySearchTree(tree)) {
cout << "CORRECT" << endl;
} else {
cout << "INCORRECT" << endl;
}
return 0;
}