0

Iam trying to Findout if this program can check if a binary tree is BST or not,

Following is the Code:

public static bool isValidBST(Node root)
    {
        return isValid(root, root.Left.Value,
             root.Right.Value);
    }

    private static bool isValid(Node node, int MIN, int MAX)
    {
        // tree with no childres is BST
        if (node == null)
            return true;

        if (node.Value <= MIN || node.Value >= MAX)
            return false;

        return isValid(node.Left, MIN, node.Value) && isValid(node.Right, node.Value, MAX);    
    }

I Think there is somthing missing in my code for example i dont think this code would work on a tree with one root and just two nodes. can you guys help me to fix my implementation?

I also found this solution on stackoverflow

private static bool isValid(Node node, int MIN, int MAX)
    {
        // tree with no childres is BST
        if (node == null)
            return true;

        if (node.Value > MIN && node.Value < MAX
            && isValid(node.Left, MIN, Math.Min(node.Value, MAX))
            && isValid(node.Right, Math.Max(node.Value, MIN), MAX))
            return true;
        else
            return false;
    }

But this won't work for me eather!

this is how i tried the Code:

 public static void Main(string[] args)
    {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        Console.WriteLine(isValidBST(n2));
        Console.ReadLine();
    }

The result is False,while it should be True.

6
  • So what happens when you run that code on a 1 node tree? You say you don't think it will work; but have you actually tried it and seen what happens? Commented Nov 13, 2015 at 20:45
  • @Servy yes i did bro, get false Commented Nov 13, 2015 at 20:49
  • 1
    And which of the nodes are validated correctly, and which are validated incorrectly when you debugged the program and looked at how each node was validated? Commented Nov 13, 2015 at 20:51
  • even better question what happens when you use the Debugger and step through the code can you find out where your logical flaw is happening..? Commented Nov 13, 2015 at 20:51
  • 1
    If you step with the debugger, you'll see what condition is returning false, and then after analyzing it you should be able to find where the bug is. Commented Nov 13, 2015 at 21:25

1 Answer 1

3

You have the error in the starting point of your solution:

public static bool isValidBST(Node root)
{
    return isValid(root, root.Left.Value,
        root.Right.Value);
}

Instead of passing root.Left.Value and root.Right.Value in the recursive function, send int.MaxValue and int.MinValue. There are at least two good reasons for doing so:

  • if root node does not have left or right child, your approach will cause NullReferenceException
  • by passing int.MaxValue and int.MinValue, you require from the left and right child only to be less than / greater than its parent, without the other boundary. For example, you shouldn't care whether the first left child is greater than some specific value, it just have to be less than the root value! By sending int.MinValue you make sure that it is always greater than that value, so you are just checking the upper bound.
Sign up to request clarification or add additional context in comments.

4 Comments

is there is a better solution than this ?
I do not think that the Math.Min\Max is necessary. If you already do check that if (node.Value <= MIN || node.Value >= MAX) return false; then you guarantee that node.Value is smaller than Max and bigger than Min.
@Klark You are right, I have made a stupid mistake. Thanks for pointing it out, I have edited the answer.
@Kob_24 In terms of time complexity - no, since you need to check all nodes in the tree to check if it is BST, therefore O(N).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.