Recursive Search Binary Tree C#

Question

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.

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? — Servy
– Servy, Commented Nov 13, 2015 at 20:45
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? — Servy
– Servy, 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..? — MethodMan
– MethodMan, Commented Nov 13, 2015 at 20:51
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. — Ivan Stoev
– Ivan Stoev, Commented Nov 13, 2015 at 21:25

Miljen Mikic · Accepted Answer · 2015-11-13 23:32:54Z

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.

edited Nov 13, 2015 at 23:32

answered Nov 13, 2015 at 21:37

Miljen Mikic

15.3k8 gold badges64 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Kob_24 Over a year ago

is there is a better solution than this ?

Klark Over a year ago

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.

Miljen Mikic Over a year ago

@Klark You are right, I have made a stupid mistake. Thanks for pointing it out, I have edited the answer.

Miljen Mikic Over a year ago

@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).

Collectives™ on Stack Overflow

Recursive Search Binary Tree C#

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related