Question
The Tree of Order
In a quiet village, there is a special Tree of Order. The villagers say the tree is a Binary Search Tree (BST) only if it follows a simple rule:
-
Every node’s left side must contain values smaller than the node.
-
Every node’s right side must contain values greater than the node.
-
And both sides must follow this rule all the way down.
You are given the root of such a tree.
Your task is to check whether this tree is truly a Binary Search Tree (BST).
Input
Your Task
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function isBST(), which takes the root as the input parameter.
Custom Input
The first line of input contains an integer, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function isBST(), which takes the root as the input parameter.
Custom Input
The first line of input contains an integer, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Output
Returns true if the given binary tree is BST, else returns false.
Example
Input:
3
2 1 3
Output:
1
Explanation:
The left subtree of root node contains node
with key lesser than the root nodes key and
the right subtree of root node contains node
with key greater than the root nodes key.
Hence, the tree is a BST.
Input:
5
5 1 4 -1 -1 3 6
Output:
0
Explanation:
3 is present on 5 right
3
2 1 3
Output:
1
Explanation:
The left subtree of root node contains node
with key lesser than the root nodes key and
the right subtree of root node contains node
with key greater than the root nodes key.
Hence, the tree is a BST.
Input:
5
5 1 4 -1 -1 3 6
Output:
0
Explanation:
3 is present on 5 right