Questions please see HackerRank. It was too long.
In simple, how can you check if a tree is a binary search tree?
Idea
Read the binary search tree from leftmost to rightmost, and make sure the order is always increasing. If you still remember how to do an in-order recursive visit for a tree. Then it is not hard. The hard thing is that how you can code it elegantly.
Solution
/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.
The Node class is defined as follows:
class Node {
int data;
Node left;
Node right;
}
*/
class IncrChecker {
private Set<Integer> visited = new HashSet();
private int max = Integer.MIN_VALUE;
public boolean isValid(int input) {
if (visited.contains(input)) return false;
if (input < max) return false;
max = input;
visited.add(input);
return true;
}
}
boolean check(Node node, IncrChecker c) {
if (node == null) return true;
return check(node.left, c) && c.isValid(node.data) && check(node.right, c);
}
boolean checkBST(Node root) {
IncrChecker checker = new IncrChecker();
return check(root, checker);
}
