Earth Hour

Sunday, April 17, 2011

Finding whether a Binary tree is BST or not

Hi folks!
It has been quite sometime since I posted on this blog. Anyways, yesterday a friend asked me this question, given a binary tree (not necessarily Binary Search Tree) find whether it is BST(Binary Search Tree) or not.
Well, the question is pretty straight forward. A small thought on the basic definition of BST will lead us to answer this. As we know, BST holds the property that for every node of the tree its left child (if exists) contains value strictly less than the current node and its right child (if exists) contains value strictly greater than the current code.
Now, if we implement the above logic we may end up marking the below tree as bst which is wrong:-

4 10
2 12

A little thought on this reveals the problem with above logic is we are not checking the range for every node. So here goes my C++ implementation (but pretty straight forward. Pardon the syntax errors) with range checking:-
Let the structure of every node is:

struct bst{
int val;
bst *left;
bst *right;

So now our function goes:

bool isbst(const bst *T,const int &start, const int &end){
return true; //trivially true for empty tree

if(start <= T->val && T->val <= end){ //check current node lies within range [start,end]
bool left = isbst(T->left, start,T->val-1); //check left subtree is bst
bool right = isbst(T->right, T->val+1,end); //check right subtree is bst
if(left && right)
return true;
return false; //value out of range;

return false; //never reached

This function is called like : isbst(root_node, INT_MIN, INT_MAX);
INT_MIN here signifies -infinity and INT_MAX as +infinity
Feedback welcome :)

Wednesday, April 7, 2010

Finding the 'First Common Ancestor' in a Binary Tree

Just this morning, I received a basic question related to Binary Trees(not necessarily Binary 'Search' Trees) from a fellow at an algorithm forum. So here I am posting my solution to it.
The problem goes like this(pretty simple 1 line problem):- Given a Binary Tree (not necessarily Binary 'Search' Tree), its root and pointers to any 2 nodes of the tree, find out the first common ancestor of the Tree. A Node of the tree contains: data, left subtree pointer, right subtree pointer but no 'Parent pointer'.

Logic: Let 'A' and 'B' be the given too node whose common ancestor we have to find. Now perform an inorder traversal of the tree and at every node call the 'search(A)' function on the left subtree and search(B) function on the right subtree. When both the results are true, you can be assured that this current node is only the first common ancestor of A, and B,
Reason: Let the first common ancestor node be 'C'. Then below C on either of its subtree tree (left and right) one and only one of the nodes amongst A and B will be present and above the hierarchy of node C, both A and B will exist on just the 1 side.
Heres d pseudo code:

function getFirstCommonAncestor(root, A, B):
if root == NULL:
return NULL // the tree doesnt exists

// if the left subtree contains node A and the right subtree contains node B then we have found the first common ancestor
if(searchTree(root.left, A) and searchTree(root.right, B)):
return root

//else recursively find the common ancestor on its left and right subtrees and return if found
L = getFirstCommonAncestor(root.left, A, B)
R = getFirstCommonAncestor(root.right, A, B)

if L != None:
return L
if R != None:
return R

return None

Well, the algorithm is not so efficient but solves our purpose partially. I am yet to further include additional conditional checks and optimize the algorithm, but for most of the cases it works just fine. :)

Here goes the complete implementation in Python.

Note: Some of the extra checks are missing. You will figure that out yourself.

Bye for now.
Happy Coding !