binary search tree find if value exists

Question

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?

You basically need to check if the value matches and if not determine if it's larger or smaller and recursively call the method on the left or right node respectively. — juharr, Sep 24 '17 at 02:31
If the Left or Right is `null` then the value doesn't exist and you don't check the other one. Instead check for `null` up front. — juharr, Sep 24 '17 at 02:44
when I call contains() again it only passes in the the leaf not the entire node which causes a null — John, Sep 24 '17 at 02:45
@John Please do not try to delete your question by blanking the content. If you really want to delete it then use the delete button. — Dai, Sep 24 '17 at 05:03

juharr · Accepted Answer · 2019-01-29T03:51:53.503

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.

score 0 · Answer 2 · answered Sep 24 '17 at 02:42

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

Thanks for the reply...I think ive tried what you have suggest in my update of OP but when I call contains() again it only passes in the the leaf not the entire node which causes a null — John, Sep 24 '17 at 02:43
Yeah, was just a conceptual reference. Glad to see you got it worked out. — bazzells, Sep 24 '17 at 03:03

binary search tree find if value exists

2 Answers2