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++ 

	#include <iostream>
	using namespace std;
	struct node {
	node *parent;
	node *left;
	node *right;
	int value;
	node(int v) : value(v), parent(0), left(0), right(0){}
	};
	bool search(node *p, node * cur)
	{
	if (!cur)
	return true;
	if (cur->parent != p)
	return false;
	if (p)
	{
	if (p->left == cur && p->value < cur->value)
	return false;
	else if (p->right == cur && p->value >= cur->value)
	return false;
	}
	if (!search(cur, cur->left))
	return false;
	if (!search(cur, cur->right))
	return false;
	return true;
	}
	int main()
	{
	node * n5 = new node(5);
	node * n3 = new node(3);
	node * n1 = new node(1);
	node * n4 = new node(4);
	node * n8 = new node(8);
	node * n6 = new node(6);
	node * n9 = new node(9);
	n5->left = n3;
	n3->parent = n5;
	n5->right = n8;
	n8->parent = n5;
	n3->left = n1;
	n1->parent = n3;
	n3->right = n4;
	n4->parent = n3;
	n8->left = n6;
	n6->parent = n8;
	n8->right = n9;
	n9->parent = n8;
	cout << "Is the tree a BST : " << search(0, n5) << endl;
	n5->left = n3;
	n3->parent = n5;
	n5->right = n8;
	n8->parent = n5;
	n3->left = n4;
	n4->parent = n3;
	n3->right = n1;
	n1->parent = n3;
	n8->left = n6;
	n6->parent = n8;
	n8->right = n9;
	n9->parent = n8;
	cout << "Is the tree2 a BST : " << search(0, n5) << endl;
	return 1;
	}

view raw check_if_btree_with_parent.cpp hosted with ❤ by GitHub

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.

	from collections import deque
	class Node:
	def __init__(self, value):
	self.value = value
	self.parent = self.left = self.right = None
	class BstChecker:
	def is_bst(self, root):
	return self.binary_search(None, root)
	def binary_search(self, parent, current):
	if current == None:
	return True
	if parent != None:
	if current.parent != parent:
	return False
	elif parent.left == current and parent.value < current.value:
	return False
	elif parent.right == current and parent.value > current.value:
	return False
	if self.binary_search(current, current.left) != True:
	return False
	if self.binary_search(current, current.right) != True:
	return False
	return True
	a = Node('a')
	b = Node('b')
	c = Node('c')
	d = Node('d')
	e = Node('e')
	f = Node('f')
	g = Node('g')
	# binary search try case
	d.left = b
	d.right = f
	b.parent = f.parent = d
	b.left = a
	b.right = c
	a.parent = c.parent = b
	f.left = e
	f.right = g
	e.parent = g.parent = f
	checker = BstChecker()
	print ("binary tree = {}".format(checker.is_bst(d)))
	# non binary search try case
	d.left = b
	d.right = f
	b.parent = f.parent = d
	b.left = c
	b.right = a
	a.parent = c.parent = b
	f.left = e
	f.right = g
	e.parent = g.parent = f
	print ("binary tree = {}".format(checker.is_bst(d)))

view raw binary_search_tree_checker.py hosted with ❤ by GitHub

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

	'''
	https://en.wikipedia.org/wiki/Binary_search_tree
	https://cseweb.ucsd.edu//~kube/cls/100/Lectures/lec5.bst/lec5-1.html
	'''
	class Node:
	def __init__(self, parent, value):
	self.value = value
	self.parent = parent
	self.left = None
	self.right = None
	def check_binary_tree(parent, child):
	if child is None:
	return True
	if parent != child.parent:
	print("parent is different")
	return False
	if parent.left == child and parent.value <= child.value:
	return False
	if parent.right == child and parent.value >= child.value:
	return False
	is_binary = check_binary_tree(child, child.left)
	if is_binary == True:
	return check_binary_tree(child, child.right)
	return is_binary
	def verify_bst(root):
	is_binary = check_binary_tree(root, root.left)
	if is_binary == True:
	return check_binary_tree(root, root.right)
	return is_binary
	root = Node(None, 10)
	c6 = Node(root, 6)
	c13 = Node(root, 13)
	root.left = c6
	root.right = c13
	c3 = Node(c6, 3)
	c7 = Node(c6, 7)
	c6.left = c3
	c6.right = c7
	c11 = Node(c13, 11)
	c14 = Node(c13, 14)
	c13.left = c11
	c13.right = c14
	c1 = Node(c3, 1)
	c4 = Node(c3, 4)
	c3.left = c1
	c3.right = c4
	c8 = Node(c7, 8)
	c7.right = c8
	is_binary = verify_bst(root)
	print("is the tree binary = {}".format(is_binary))

view raw check_if_bst.py hosted with ❤ by GitHub