Question on binary search tree

Question

Hi,

I am looking at the following code: http://netrsc.blogspot.com/2010/04/net-c-binary-tree.html

Am I right in thinking that the while (!Found) condition will iterate the tree?

protected void Insert(T item)
{
    TreeNode<T> TempNode = Root;
    bool Found=false;
    while (!Found)
    {
        int ComparedValue = TempNode.Value.CompareTo(item);
        if(ComparedValue<0)
        {
            if(TempNode.Left==null)
            {
                TempNode.Left=new TreeNode<T>(item,TempNode);
                ++NumberOfNodes;
                return;
            }
            else
            {
                TempNode=TempNode.Left;
            }
        }
        else if(ComparedValue>0)
        {
            if(TempNode.Right==null)
            {
                TempNode.Right=new TreeNode<T>(item,TempNode);
                ++NumberOfNodes;
                return;
            }
            else
            {
                TempNode=TempNode.Right;
            }
        }
        else
        {
            TempNode=TempNode.Right;
        }
    }
}

Also, for the find and traversal methods, how do these work? If nothing is returned from the Traversal method but from the left branch, would the loop in Find execute again? How would it know to execute down the right branch?

protected IEnumerable<TreeNode<T>> Traversal(TreeNode<T> Node)
{
    if (Node.Left != null)
    {
        foreach (TreeNode<T> LeftNode in Traversal(Node.Left))
            yield return LeftNode;
    }
    yield return Node;
    if (Node.Right != null)
    {
        foreach (TreeNode<T> RightNode in Traversal(Node.Right))
            yield return RightNode;
    }
}

Thanks

Answer 1

Not necessarily. It will only iterate through the nodes on the path of where the inserted node should be added. There are some return statements sprinkled in that loop so it will essentially stop when it find's the correct location and adds the new node. It would have been more appropriate (in the code) to set the Found variable to true instead.

The traversal methods return the nodes of both the left and right subtrees. You should note that it uses yield return and not the plain return. Using it creates an enumerator where each item that is yielded is what the numerator would return as you iterate through it. Think of it as pausing execution when it reaches a yield return statement. When iterating to the next value from the calling code, execution is continued at that point potentially returning more values.

Find will take the results of the traversal and returns the stored value if found in one of the nodes.

Answer 2

An example of iterating the tree is in the Find command, which calls the Traversal function.

foreach (TreeNode<T> Item in Traversal(Root))

The Traversal function will iteratively return the items in the tree in a depth-first, left-to-right manner. If you look at the Traversal code, it calls itself recursively on the left side and then recursively on the right.

Traversal returns the entire tree in an iterable object, where the items are ordered depth-first, left-to-right. The Find command simply loops through each one and when it hits a match returns it breaking out of the loop. Basically, Traversal returns an ordered iterable of items, Find goes through that list looking for a match. Find really doesn't even have to know whether it's searching through a list or a tree or whatever. It just needs something to iterate through to find a match.