top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to find if given binary tree is a valid binary search tree?

+4 votes
177 views

Assuming that each node contains a pointer to its left child, a pointer to its right child, and an integer, but not a pointer to its parent? How to find out if given tree is a binary tree or not.

posted Sep 28, 2013 by Vivek Singh

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Which language or just algorithm.

2 Answers

+4 votes
boolean isValidTree(Node *root) 
{
    if (root->left)
        if (root->left->data > root->data) ||  (!isValidTree(root->left))
                return FALSE;

    if (root->right)
        if (root->right->data < root->data) || (!isValidTree(root->right))
                return FALSE;               

    return TRUE;
}
answer Oct 10, 2013 by Vikas Upadhyay
+2 votes

Note that it is not enough to write a recursive function that just checks if the left and right nodes of each
node are less than and greater than the current node (and calls that recursively). You need to make sure that all the nodes of the subtree starting at your current node are within the valid range of values allowed
by the current node's ancestors. Therefore you can solve this recursively by writing a helper function that accepts a current node, the smallest allowed value, and the largest allowed value for that subtree.
Example for this:-

boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
return true;
}

The running time of this algorithm is O(n).

answer Sep 28, 2013 by Arvind Singh
Is it (curr.left.value) ok in c.
because left is pointer.

if (curr.right.value > max || !isValidHelper(curr.right, curr.value, max))

If "curr.right.value" is greate than "max" then function "isValidHelper" will not be called because of short circuit .

Please refer the following link
http://www.gnu.org/software/octave/doc/interpreter/Short_002dcircuit-Boolean-Operators.html

I think you can improve performance of your code in terms of Space complexity.
There is no need to pass value min and max in function.
It will increase the size of stack by 8 byte every time.
So if there are "N" node in tree then you are using NX8 byte extra.

I am posting the improved code.
Please correct me if I am wrong.
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...