Recipe 10.6 Creating a Binary Tree

Problem

You need to store information in a tree structure, where the left node is less than its parent node, and the right node is greater than or equal to (in cases where the tree can contain duplicates) its parent. The stored information must be easily inserted into the tree, removed from the tree, and found within the tree.

Solution

Each node must be an object that inherits from the IComparable interface. This means that every node that wishes to be included in the binary tree must implement the CompareTo method. This method will allow one node to determine whether it is less than, greater than, or equal to another node.

Use the following BinaryTree class, which contains all of the nodes in a binary tree and lets you traverse it:

using System;
using System.Collections;

public class BinaryTree
{
    public BinaryTree( ) {}

    public BinaryTree(IComparable value, int index) 
    {
        BinaryTreeNode node = new BinaryTreeNode(value, index);
        root = node;
        counter = 1;
    }

    // Use this .ctor when you need to flatten this tree (see recipe 9.15)
    public BinaryTree(IComparable value) 
    {
        BinaryTreeNode node = new BinaryTreeNode(value);
        root = node;
        counter = 1;
    }

    protected int counter = 0;             // Number of nodes in tree
    protected BinaryTreeNode root = null;  // Pointer to root node in this tree

    public  void AddNode(IComparable value, int index)
    {
        BinaryTreeNode node = new BinaryTreeNode(value, index);
        ++counter;

        if (root == null)
        {
            root = node;
        }
        else
        {
            root.AddNode(node);
        }
    }

    // Use this method to add a node 
    //    when you need to flatten this tree (see recipe 9.15)
    public int AddNode(IComparable value)
    {
        BinaryTreeNode node = new BinaryTreeNode(value);
        ++counter;

        if (root == null)
        {
            root = node;
        }
        else
        {
            root.AddNode(node);
        }

        return (counter - 1);
    }

    public BinaryTreeNode SearchDepthFirst(IComparable value)
    {
        return (root.DepthFirstSearch(value));
    }

    public void Print( )
    {
        root.PrintDepthFirst( );
    }

    public BinaryTreeNode GetRoot( )
    {
        return (root);
    }

    public int TreeSize
    {
        get {return (counter);}
    }        
}

The BinaryTreeNode encapsulates the data and behavior of a single node in the binary tree:

public class BinaryTreeNode
{
    public BinaryTreeNode( ) {}

    public BinaryTreeNode(IComparable value)
    {
        nodeValue = value;
    }

    // These 2 ctors Added to allow tree to be flattened
    public BinaryTreeNode(int index) 
    {
        nodeIndex = index;
    }

    public BinaryTreeNode(IComparable value, int index)
    {
        nodeValue = value;
        nodeIndex = index;
    }

    protected int nodeIndex = 0;         // Added to allow tree to be flattened
    protected IComparable nodeValue = null;
    protected BinaryTreeNode leftNode = null;     //  leftNode.Value < Value
    protected BinaryTreeNode rightNode = null;    //  rightNode.Value >= Value

    public int NumOfChildren
    {
        get {return (CountChildren( ));}
    }

    public int CountChildren( )
    {
        int currCount = 0;

        if (leftNode != null)
        {
            ++currCount;
            currCount += leftNode.CountChildren( );
        }

        if (rightNode != null)
        {
            ++currCount;
            currCount += rightNode.CountChildren( );
        }

        return (currCount);
    }

    public int Index
    {
        get {return (nodeIndex);}
    }

    public BinaryTreeNode Left
    {
        get {return (leftNode);}
    }

    public BinaryTreeNode Right
    {
        get {return (rightNode);}
    }

    public IComparable GetValue 
    {
        get {return (nodeValue);}
    }

    public void AddNode(BinaryTreeNode node)
    {
        if (node.nodeValue.CompareTo(nodeValue) < 0)
        {
            if (leftNode == null)
            {
                leftNode = node;
            }
            else
            {
                leftNode.AddNode(node);
            }
        }
        else if (node.nodeValue.CompareTo(nodeValue) >= 0)
        {
            if (rightNode == null)
            {
                rightNode = node;
            }
            else
            {
                rightNode.AddNode(node);
            }
        }
    }

    public bool AddUniqueNode(BinaryTreeNode node)
    {
        bool isUnique = true;

        if (node.nodeValue.CompareTo(nodeValue) < 0)
        {
            if (leftNode == null)
            {
                leftNode = node;
            }
            else
            {
                leftNode.AddNode(node);
            }
        }
        else if (node.nodeValue.CompareTo(nodeValue) > 0)
        {
            if (rightNode == null)
            {
                rightNode = node;
            }
            else
            {
                rightNode.AddNode(node);
            }
        }
        else   //node.nodeValue.CompareTo(nodeValue) = 0
        {
            isUnique = false;
            // Could throw exception here as well...
        }

        return (isUnique);
    }

    public BinaryTreeNode DepthFirstSearch(IComparable targetObj)
    {
        // NOTE: foo.CompareTo(bar) == -1   -->   (foo < bar)
        BinaryTreeNode retObj = null;
        int comparisonResult = targetObj.CompareTo(nodeValue);

        if (comparisonResult  == 0)
        {
            retObj = this;
        }
        else if (comparisonResult > 0)
        {
            if (rightNode != null)
            {
                retObj = rightNode.DepthFirstSearch(targetObj);
            }
        }
        else if (comparisonResult < 0)
        {
            if (leftNode != null)
            {
                retObj = leftNode.DepthFirstSearch(targetObj);
            }
        }

        return (retObj);
    }

    public void PrintDepthFirst( )
    {
        if (leftNode != null)
        {
            leftNode.PrintDepthFirst( );
        }

        Console.WriteLine(this.nodeValue.ToString( ));

        try
        {
            Console.WriteLine("\tContains Left: " + 
            leftNode.nodeValue.ToString( ));
        }
        catch
        {
            Console.WriteLine("\tContains Left:  NULL");
        }
        try
        {
            Console.WriteLine("\tContains Right: " + 
            rightNode.nodeValue.ToString( ));
        }
        catch
        {
            Console.WriteLine("\tContains Right: NULL");
        }

        if (rightNode != null)
        {
            rightNode.PrintDepthFirst( );
        }
    }

    public void RemoveLeftNode( )
    {
        leftNode = null;
    }

    public void RemoveRightNode( )
    {
        rightNode = null;
    }
}

The methods defined in Table 10-4 are of particular interest to using a BinaryTree object.

Table 10-4. Members of the BinaryTree class

Member	Description
Overloaded constructor	This constructor creates a BinaryTree object with a root node and a node index id. Its syntax is: BinaryTree(IComparable value, int index) where value is the root node for the tree, and index is used for flattening the tree.
Overloaded constructor	This constructor creates a BinaryTree object with a root node. Its syntax is: BinaryTree(IComparable value) where value is the root node for the tree. Note that this tree may not be flattened.
AddNode method	Adds a node to the tree. Its syntax is: AddNode(IComparable value, int id) where value is the object to be added and id is the node index. Use this method if the tree will be flattened.
AddNode method	Adds a node to the tree. Its syntax is: AddNode(IComparable value) where value is the object to be added. Use this method if the tree will not be flattened.
SearchDepthFirst method	Searches for and returns a BinaryTreeNode object in the tree, if one exists. This method searches the depth of the tree first. Its syntax is: SearchDepthFirst(IComparable value) where value is the object to be found in the tree.
Print method	Displays the tree in depth-first format. Its syntax is: Print( )
GetRoot method	Returns the BinaryTreeNode object that is the root of the tree. Its syntax is: GetRoot( )
TreeSize property	A read-only property that gets the number of nodes in the tree. Its syntax is: int TreeSize {get;}

The methods defined in Table 10-5 are of particular interest to using a BinaryTreeNode object.

Table 10-5. Members of the BinaryTreeNode class

Member	Description
Overloaded constructor	This constructor creates a BinaryTreeNode object. Its syntax is: BinaryTreeNode(IComparable value) If a tree is to be flattened, the following constructors should be used instead: BinaryTreeNode(int nodeIndex) BinaryTreeNode(IComparable value, int nodeIndex) where value is the object contained in this node, which will be used to compare to its parent. The nodeIndex is used for flattening the tree.
NumOfChildren property	A read-only property to retrieve the number of children below this node. Its syntax is: int NumOfChildren {get;}
Index property	A read-only property to retrieve the index number of this node. This index value was set in the nodeIndex parameter of its constructor. Its syntax is: int Index {get;}
Left property	A read-only property to retrieve the left child node below this node. Its syntax is: BinaryTreeNode Left {get;}
Right property	A read-only property to retrieve the right child node below this node. Its syntax is: BinaryTreeNode Right {get;}
CountChildren method	Retrieves the number of child nodes below this node. Its syntax is: CountChildren( )
GetValue method	Returns the IComparable object that this node contains. Its syntax is: GetValue( )
AddNode method	Adds a new node recursively to either the left or right side. Its syntax is: AddNode(BinaryTreeNode node) where node is the node to be added. Duplicate nodes may be added using this method.
AddUniqueNode method	Adds a new node recursively to either the left side or the right side. Its syntax is: AddUniqueNode(BinaryTreeNode node) where node is the node to be added. Duplicate nodes may not be added using this method. A Boolean value is returned; true indicates a successful operation, false indicates an attempt to add a duplicate node.
DepthFirstSearch method	Searches for and returns a BinaryTreeNode object in the tree, if one exists. This method searches the depth of the tree first. Its syntax is: DepthFirstSearch(IComparable targetObj) where targetObj is the object to be found in the tree.
PrintDepthFirst method	Displays the tree in depth first format. Its syntax is: PrintDepthFirst( )
RemoveLeftNode method	Removes the left node and any child nodes of this node. Its syntax is: RemoveLeftNode( )
RemoveRightNode method	Removes the right node and any child nodes of this node. Its syntax is: RemoveRightNode( )

The following code illustrates the use of the BinaryTree and BinaryTreeNode classes when creating and using a binary tree:

public static void TestBinaryTree( )
{
    BinaryTree tree = new BinaryTree("d");
    tree.AddNode("a");
    tree.AddNode("b");
    tree.AddNode("f");
    tree.AddNode("e");
    tree.AddNode("c");
    tree.AddNode("g");
    
    tree.Print( );
    tree.Print( );

    Console.WriteLine("tree.TreeSize: " + tree.TreeSize);            
    Console.WriteLine("tree.GetRoot( ).DepthFirstSearch(a).NumOfChildren: " + 
            tree.GetRoot( ).DepthFirstSearch("b").NumOfChildren);            
    Console.WriteLine("tree.GetRoot( ).DepthFirstSearch(a).NumOfChildren: " + 
            tree.GetRoot( ).DepthFirstSearch("a").NumOfChildren);            
    Console.WriteLine("tree.GetRoot( ).DepthFirstSearch(g).NumOfChildren: " + 
            tree.GetRoot( ).DepthFirstSearch("g").NumOfChildren);            

    Console.WriteLine("tree.SearchDepthFirst(a): " + 
            tree.SearchDepthFirst("a").GetValue.ToString( ));
    Console.WriteLine("tree.SearchDepthFirst(b): " + 
            tree.SearchDepthFirst("b").GetValue.ToString( ));
    Console.WriteLine("tree.SearchDepthFirst(c): " + 
            tree.SearchDepthFirst("c").GetValue.ToString( ));
    Console.WriteLine("tree.SearchDepthFirst(d): " + 
            tree.SearchDepthFirst("d").GetValue.ToString( ));
    Console.WriteLine("tree.SearchDepthFirst(e): " + 
            tree.SearchDepthFirst("e").GetValue.ToString( ));
    Console.WriteLine("tree.SearchDepthFirst(f): " + 
            tree.SearchDepthFirst("f").GetValue.ToString( ));

    tree.GetRoot( ).RemoveLeftNode( );
    tree.Print( );

    tree.GetRoot( ).RemoveRightNode( );
    tree.Print( );
}

Discussion

Trees are data structures where each node has exactly one parent and possibly many children. The root of the tree is a single node that branches out into one or more child nodes. A node is the part of the tree structure that contains data and contains the branches (or in more concrete terms, references) to its children node(s).

A tree can be used for many things, such as to represent a management hierarchy with the president of the company at the root node and the various vice-presidents as child nodes of the president. The vice-presidents may have managers as child nodes, and so on. A tree can be used to make decisions, where each node of the tree contains a question and the answer given depends on which branch is taken to a child node. The tree described in this recipe is called a binary tree. A binary tree can have zero, one, or two child nodes for every node in the tree. A binary tree node can never have more than two child nodes; this is where this type of tree gets its name. (There are other types of trees. For instance, the n-ary tree can have zero to n nodes for each node in the tree. This type of tree is defined in Recipe 10.7.)

A binary tree is very useful for storing objects and then efficiently searching for those objects. The following algorithm is used to store objects in a binary tree:

Basically, this algorithm states that the node to the left of the current node contains an object or value less than the current node, and the node to the right of the current node contains an object or value greater than (or equal to, if the binary tree can contain duplicates) the current node.

Searching for an object in a tree is easy. Just start at the root and ask yourself, "Is the object I am searching for less than the current node's object?" If it is, follow the left branch to the next node in the tree. If it is not, check the current node to determine whether it contains the object you are searching for. If this is still not the correct object, continue down the right branch to the next node. When you get to the next node, start the process over again.

The binary tree used in this recipe is made up of two classes. The BinaryTree class is not a part of the actual tree; rather, it acts as a starting point from which we can create a tree, add nodes to it, search the tree for items, and retrieve the root node to perform other actions.

The second class, BinaryTreeNode, is the heart of the binary tree and represents a single node in the tree. This class contains all the members that are required to create and work with a binary tree.

The BinaryTreeNode class contains a protected field, nodeValue, that contains an object implementing the IComparable interface. This structure allows us to perform searches and add nodes in the correct location in the tree. The Compare method of the IComparable interface is used in searching and adding methods to determine whether we need to follow the left or right branch. See the AddNode, AddUniqueNode, and DepthFirstSearch methods to see this in action.

There are two methods to add nodes to the tree, AddNode and AddUniqueNode. The AddNode method allows duplicates to be introduced to the tree, whereas the AddUniqueNode allows only unique nodes to be added.

The DepthFirstSearch method allows the tree to be searched by first checking the current node to see whether it contains the value searched for; if not, recursion is used to check the left and then the right node. If no matching value is found in any node, this method returns null.

It is interesting to note that even though the BinaryTree class is provided to create and manage the tree of BinaryTreeNode objects, we could merely use the BinaryTreeNode class as long as we keep track of the root node ourselves. The following code creates and manages the tree without the use of the BinaryTree class:

public static void TestManagedTreeWithNoBinaryTreeClass( )
{
    // Create the root node
    BinaryTreeNode topLevel = new BinaryTreeNode("d");

    // Create all nodes that will be added to the tree
    BinaryTreeNode one = new BinaryTreeNode("b");
    BinaryTreeNode two = new BinaryTreeNode("c");
    BinaryTreeNode three = new BinaryTreeNode("a");
    BinaryTreeNode four = new BinaryTreeNode("e");
    BinaryTreeNode five = new BinaryTreeNode("f");
    BinaryTreeNode six = new BinaryTreeNode("g");

    // Add nodes to tree through the root
    topLevel.AddNode(three);
    topLevel.AddNode(one);
    topLevel.AddNode(five);
    topLevel.AddNode(four);
    topLevel.AddNode(two);
    topLevel.AddNode(six);

    // Print the tree starting at the root node
    topLevel.PrintDepthFirst( );

    // Print the tree starting at node 'Three'
    three.PrintDepthFirst( );

    // Display the number of child nodes of various nodes in the tree
    Console.WriteLine("topLevel.NumOfChildren: " + topLevel.NumOfChildren);            
    Console.WriteLine("one.NumOfChildren: " + one.NumOfChildren);            
    Console.WriteLine("three.NumOfChildren: " + three.NumOfChildren);            
    Console.WriteLine("six.NumOfChildren: " + six.NumOfChildren);            

    // Search the tree using the depth-first searching method
    Console.WriteLine("topLevel.DepthFirstSearch(a): " + 
            topLevel.DepthFirstSearch("a").GetValue.ToString( ));
    Console.WriteLine("topLevel.DepthFirstSearch(b): " + 
            topLevel.DepthFirstSearch("b").GetValue.ToString( ));
    Console.WriteLine("topLevel.DepthFirstSearch(c): " + 
            topLevel.DepthFirstSearch("c").GetValue.ToString( ));
    Console.WriteLine("topLevel.DepthFirstSearch(d): " + 
            topLevel.DepthFirstSearch("d").GetValue.ToString( ));
    Console.WriteLine("topLevel.DepthFirstSearch(e): " + 
            topLevel.DepthFirstSearch("e").GetValue.ToString( ));
    Console.WriteLine("topLevel.DepthFirstSearch(f): " + 
            topLevel.DepthFirstSearch("f").GetValue.ToString( ));

    // Remove the left child node from the root node and display the entire tree
    topLevel.RemoveLeftNode( );
    topLevel.PrintDepthFirst( );

    // Remove all nodes from the tree except for the root and display the tree
    topLevel.RemoveRightNode( );
    topLevel.PrintDepthFirst( );
}

See Also

See the "Queue Class" and "IComparable Interface" topics in the MSDN documentation.