CODEWITHSUNDEEP
c#nodes
John
John

Reputation: 3945

binary search tree find if value exists

Trying to learn tree nodes...

    Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.

Write a function that checks if a given binary search tree contains a given value.

For example, for the following tree:

n1 (Value: 1, Left: null, Right: null)
n2 (Value: 2, Left: n1, Right: n3)
n3 (Value: 3, Left: null, Right: null)
Call to Contains(n2, 3) should return true since a tree with root at n2 contains number 3.

So far iv got...

 public class BinarySearchTree
    {
        public static bool Contains(Node root, int value)
        {
            foreach (var v in root)
            {
                if (root.Value == value)
                {
                    //value found return true
                }
            }
        }

        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(Contains(n2, 3));
        }
    }

but root is flagging as unavailable and if I do root. I get the options tostring, value, left, right.

Can I not iterate through a node as I would a list? How can I check if value is found in root? thank you

UPDATE Ahh yes OK...thanks for the reply juharr so I have updated my code to...

public static bool Contains(Node root, int value)
            {
                    if (root.Value == value)
                    {
                        return true;
                    }
                    else if (root.Value > value)
                    {
                        if (root.Right == null)
                        {
                            Contains(root.Left, value);
                        }
                        Contains(root.Right, value);
                    }
                    else //(root.Value < value)
                    {
                        if (root.Left == null)
                        {
                            Contains(root.Right, value);
                        }

                        Contains(root.Left, value);
                    }

                return false;
            }

however on the second loop round root is null and causes a crash?

Upvotes: 1

Views: 23486

Answers (2)

juharr
juharr

Reputation: 32276

You're close, but this is what you actually want

public static bool Contains(Node root, int value)
{
    if (root == null) return false;
    if (root.Value == value) return true;
    if (root.Value > value) return Contains(root.Left, value);
    return Contains(root.Right, value);
}

So if the root is null then there are no numbers so you return false. Then you check if the value matches and return true if it does. Then if the value of the root is larger then return the result of the recursive call on the left sub-tree. And finally you just return the result of the recursive call on the right sub-tree because at this point you know the root value is smaller.

And here's a non-recursive way to do the search

public static bool Contains(Node root, int value)
{
    while(root != null)
    {
        if(root.Value == value) return true;
        if(root.Value > value) root = root.Left;
        else root = root.Right;
    }

    return false;
}

Here we loop until we hit a null node and simply set root to the Left or Right based on the comparison or immediately return true if the Value is a match. If we make it out the loop then the value was not found.

Upvotes: 10

bazzells
bazzells

Reputation: 329

Can I not iterate through a node as I would a list?

You can iterate through a BST - using a stack to pass over child nodes would help with that (as demonstrated here). So you could throw the children of root into a stack, and then compare their values to your target value.

With that said, the arguably more intuitive way to approach it would be recursively - where theoretically you would check the current node's value, and then recursively call Contains - passing it the current node's right or left child until you find your target Value, or don't.

In either approach, you'll want to capitalize on the advantages of a BST you pointed out in the question:

Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.

Considering this you'll be able to implement it in O(log n) time by 'cutting off' the values you know you don't need to check (due to the current node's value in relation to your target value).

Upvotes: 0

Related Questions