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, Nov 13 '15 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, Nov 13 '15 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, Nov 13 '15 at 20:51
@Servy Something is strange its returning false always and the if statement is always false.... — Kob_24, Nov 13 '15 at 20:56
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, Nov 13 '15 at 21:25

Miljen Mikic · Accepted Answer · 2015-11-13T23:32:54.683

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 '15 at 23:32

answered Nov 13 '15 at 21:37

Miljen Mikic

14,765
8
58
66

is there is a better solution than this ? – Kob_24 Nov 13 '15 at 21:58
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 Nov 13 '15 at 22:27
@Klark You are right, I have made a stupid mistake. Thanks for pointing it out, I have edited the answer. – Miljen Mikic Nov 13 '15 at 23:33
@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). – Miljen Mikic Nov 13 '15 at 23:36

Recursive Search Binary Tree C#

1 Answers1