Checking if a given tree is Binary search tree - no parent pointer[reviewed]

Problem

Your are given the pointer to the root of the tree, with nodes having the following structure.

struct node {

    node * left;

    node * right;

    int value;

};

You algorithm should find out whether the given tree is BST (Binary search tree or not)

This is the variation of the previous "Checking if a given tree is Binary search tree - with parent pointer" problem. ONLY difference is that there is no parent pointer.

In this case, we can use "In-order" traversal algorithm to check the nodes in order and store them in the array.

After the traversal, you have the array of nodes and check if the values in the array is either descending order or ascending order. If not, it is not BST.

Overall running time is O(N) with space complexity of O(N)

Here is the complete solution in C++ 

Practice statistics

15 mins: to write up the code with minor typo.


UPDATE(2019-07-27): solved the problem again. This time we use DFS and checked whether parent' value is in right place compared to its left or right child's value.

- If current node is left child, parent's value should be greater than current value.
- If current child is right child, parent's value should be smaller than current value.

We check this condition recursively.

Here is the solution in python.

Practice statistics:

10:00 to write the code
10:00: to write the test cases ( made one logic mistake found after running ... you can do it better)