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

	#include<vector>
	#include<iostream>
	using namespace std;
	struct node {
	node * right;
	node * left;
	int value;
	node (int v): value(v), right(0), left(0){}
	};
	void inorder(node * n, vector<node *>& list)
	{
	if (!n)
	return;
	inorder(n->left, list);
	list.push_back(n);
	inorder(n->right, list);
	}
	bool check_if_bst(node * root)
	{
	vector<node *>list;
	inorder(root, list);
	bool is_bst = true;
	bool ascending = false;
	for(int i = 1; i < list.size(); i++)
	{
	if (i == 1)
	ascending = (list[i-1]->value < list[i]->value);
	else if (ascending != (list[i-1]->value < list[i]->value))
	{
	is_bst = false;
	break;
	}
	}
	return is_bst;
	}
	int main()
	{
	node *t5 = new node(5);
	node *t3 = new node(3);
	node *t4 = new node(4);
	node *t2 = new node(2);
	node *t7 = new node(7);
	t5->left = t3;
	t5->right = t4;
	t3->left = t2;
	t3->right = t7;
	cout<<"tree is bst? => "<< check_if_bst(t5)<<endl;
	t5->left = t3;
	t5->right = t7;
	t3->left = t2;
	t3->right = t4;
	cout<<"tree2 is bst? => "<< check_if_bst(t5)<<endl;
	return 1;
	}

view raw check_btree_bst.cpp hosted with ❤ by GitHub

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.

	class Node:
	def __init__(self, value):
	self.value = value
	self.left = self.right = None
	class BstCheckerNoParent:
	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:
	# left child
	if parent.left == current and parent.value < current.value:
	return False
	# right child
	if 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
	checker = BstCheckerNoParent()
	a = Node(1)
	b = Node(2)
	c = Node(3)
	d = Node(4)
	e = Node(5)
	f = Node(6)
	g = Node(7)
	h = Node(8)
	i = Node(9)
	j = Node(10)
	#BST case
	d.left = b
	d.right = g
	b.left = a
	b.right = c
	g.left = f
	g.right = i
	f.left = e
	i.left = h
	i.right = j
	print("is this tree BST: {}".format(checker.is_bst(d)))
	# non BST case
	d.left = b
	d.right = g
	b.left = a
	b.right = c
	g.left = i
	g.right = f
	f.left = e
	i.left = h
	i.right = j
	print("is this tree BST: {}".format(checker.is_bst(d)))

view raw binary_search_tree_checker_with_no_parent_pointer.py hosted with ❤ by GitHub

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)