CODEWITHSUNDEEP
c#algorithmbinary-treebinary-search-tree
Kob_24
Kob_24

Reputation: 612

Recursive Search Binary Tree C#

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.

Upvotes: 0

Views: 1470

Answers (1)

Miljen Mikic
Miljen Mikic

Reputation: 15241

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.

Upvotes: 3

Related Questions