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

Problem

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

struct node {

    node * parent;

    node * left;

    node * right;

    int value;

};

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

Let's think about what BST really is. BST is a binary tree that meets the following condition:

1)  For any given node, it is guaranteed that nodes on the left side of the current node are smaller than the current node and the ones on the right are larger than the current node.

2) For any given node, the current node points to its parent and the parent points to the current node through either left or right pointer.

Given that conditions, we can perform the DFS and pass the pointer to parent for each step to validate the two conditions above.

Overall running time is O(N).

Here is the complete solution in C++ 

Practice statistics

8:30: to think up the algorithm
7:30 : to hand write the solution
8:30 : to write in the IDE


UPDATE(2019-07-26): solved the question again and misunderstood the properties of BST.
I initially thought BST should not be circular graph. So my code check if there is any circular relationship vis BFS.

Rewrote the code to properly check the validity of BST.

Here is a solution in python.


Practice statistics

After examining the algorithm, spent 15 mins to write the code again.
Made mistakes in test code and logic as well. (This should not happen)

UPDATE (2022-06-08): solved the question again and misunderstood the characteristics of the binary search tree.  took 27 mins to come up with the wrong solution and took another 30 mins to write the correct solution after minor bug fix.

Key characteristics of binary search tree:

For every node, X in the BST,

- key of X is larger than all keys in the left tree of X

- key of X is smaller than all keys in the right tree of X

Here is the complete code in python