Searching through Objects in binary tree with String parameters and generic type T

Question

So I'm trying to search through a binary tree filled with a Country object stored in the node as T Data. The Country object as has String variable containing the name of the country (countryName), I want to search in a textbox for the countryName and to return a boolean value. So it would traverse the binary tree of Country objects and match the value in the textbox field with the countryName. One could store the values of the object separately in the nodes but I'd rather use generic types. Below are my searching methods.

public Boolean Contains(T item)
{
    return contains(item, ref root);
}

private Boolean contains(T item, ref Node<T> tree)
{
    if (tree != null)
    {
        if (item.CompareTo(tree.Data)==0)
        {
            Console.WriteLine("Found");
            return true;
        }
        return contains(item, ref tree.Left) || contains(item, ref tree.Right);
    }
    else
    {
        return false;
    }
}

And the Node structure

public T Data;
public Node<T> Left;
public Node<T> Right;
public int balanceFactor;
public Node(T Data)
{
    this.Data = Data;
    Left = null;
    Right = null;
}

Any reason you're passing `tree` by reference? Also, I *suspect* the answer is simply to accept an `IComparer` in your constructor, but it's not really clear at the moment. Are you expecting to pass just the name of the country into `Contains`, or a country *with* that name? — Jon Skeet, Apr 13 '18 at 10:16
Worth [to read](https://learn.microsoft.com/en-us/dotnet/standard/design-guidelines/capitalization-conventions). — Sinatr, Apr 13 '18 at 10:19
@DaisyShipton I have `where T : IComparable` in the class header. For your second question, if I'm understanding correctly, it's the latter. The user enters text into the text field and the program should traverse the binary tree and determine whether a Country object with that specific countryName, exists. — badprogramming99, Apr 13 '18 at 10:33
Do does your `Country` implement `IComparable` by comparing by name? If you could provide a [mcve] it would make it a lot easier to help you. It's not even clear what you're asking at the moment - does your code work but you want to change it, or not work at all? Also it sounds like `Node` is a class, not a structure. — Jon Skeet, Apr 13 '18 at 10:38

Prime · Answer 1 · 2018-04-13T11:01:39.320

Never call a function inside of itself, this will eventually cause a StackOverflowException. You should do something like this instead;

Depth First Search using `Stack<T>`

static bool Contains<T>(T item, Node<T> tree) {
    Stack<Node<T>> stack = new Stack<Node<T>>();

    stack.Push(tree); //Push the root node into the stack

    Node<T> current;
    do {
        current = stack.Pop(); //Get the last item that was added to the stack and remove it at the same time

        if (item.Equals(current.Data)) //If the item we just popped has its 'Data' property equal to the 'item'
        {
            Console.WriteLine("Found");
            return true; //then return true
        }

        //Otherwise add the left and right nodes to the stack if they exist.
        if(current.Left != null) stack.Push(current.Left);
        if(current.Right != null) stack.Push(current.Right);
    } while(stack.Count > 0); //If the stack still contains items, go back to the 'do'

    //If we've reached this point we've searched the entire tree and found nothing
    return false;
}

Dotnetfiddle usage example

When you execute a function in a program the program needs some way of storing where it was, this is called the stack. Stacks generally have a limited size of how large they can be, and if you reach this limit and you attempt to go one depth further it will throw a StackOverflowException.

Basically this is how your function looks in operation:

contains(contains(contains(contains(contains(contains(contains(contains(...

The amount of levels of depth it has to account for will not typically occur in an application unless you're doing something wrong like calling a function inside of itself, which is what you're doing.

So instead of making the stack go to crazy levels of depth, let's just keep a list of all of the stuff we need to compare to what we're searching, and along the way add their children to the same list.

This is where the Stack<T> type comes in. The Stack type, despite sharing a name with the stack of the program, are not the same thing. The Stack type is just a list of items that has the ability to add (Push(T)), as well as retrieve the last item that was added to the list while removing it from the list at the same time (Pop()).

So instead of going a level of depth down every time we want to search a node, we instead just add it to a Stack while looping it.

score 0 · Answer 2 · answered Apr 13 '18 at 11:56

In binary search tree (BST) you must compare items in a way that gives you same sorting order (using same comparer) when you insert/search/delete an item. You can't use one comparer (for example, that compares countries population) in insert and than search country by name in the same BST in O(lg(N)).

In order to build BST that allows you to search country by name use either procedure argument like Func<of T, of T, of int> or very common in .NET Framework IComparer<of T> in tree constructor. See SortedSet<of T> class design and SortedSet<of T>(IComparer<of T>) constructor specifically.

Example implementation:

Node<T> _root;
readonly IComparer<T> _comparer;

public bool Contains(T target)
{
    return Contains(_root, target);
}

bool Contains(Node<T> root, T target)
{
    if (root == null)
        return false;
    int cmp = _comparer.Compare(target, root.Data);
    if (cmp == 0)
        return true;
    return cmp < 0 ? Contains(root.Left, target) : Contains(root.Right, target);
}

Also note t in your BST search implementation it is crutial for performance to make recursive call only on a single subtree (left or right).

For more information check Binary search tree page on Wikipedia, SortedSet - custom order when storing a class object and Using lambda expression in place of IComparer argument discussions on StackOverflow.

Searching through Objects in binary tree with String parameters and generic type T

2 Answers2

Depth First Search using Stack<T>

Depth First Search using `Stack<T>`