Hi all.

I've been working on a Binary Search Tree as a beginner and have the majority of functions working, however in the program I need to give the option to choose how to traverse the contents and then display them in that order. I've got the traversal methods, however I can't get my balancing to work properly and so the results don't come out in the right order.

I've been changing things around trying to get it to work, here's how i've got it the moment, in which when requesting a traversal I get an error in the command line saying "Object reference not set to an instance of an object." The main problem i've been having is how and where to invoke the balance method in order to sort and traverse.

I've searched all over the place but can't seem to find anything that I can get working in my code.

Below are my classes - could any of you give me a hand with how to get this working please? Apologies for the lack of comments in the code.

Here is my BinaryTree class:

//‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
///
/// Binary Tree data structure
/// Begin Binary Tree structure definition
///
// ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
using System;
using csKicksTreeApp;
class BinaryTree
{
    private BinaryTreeNode head;
    private int size;
    //private int depth;
    ///
    /// Constructor ‐ Creates a new instance of a Binary Tree
    ///
    public BinaryTree()
    {
        head = null;
        size = 0;
    }
    ///
    /// Gets or sets the root of the tree (the top‐most node)
    ///
    public BinaryTreeNode Root
    {
        get { return head; }
        set { head = value; }
    }
    ///
    /// Gets the number of elements stored in the tree
    ///
    public int Count
    {
        get { return size; }
    }
    ///
    /// Adds a new element to the tree
    ///
    public void Add(Int32 value)
    {
        BinaryTreeNode node = new BinaryTreeNode(value);
        this.Add(node);
    }
    ///
    /// Adds a node to the tree
    ///

    public void Add(BinaryTreeNode node) //Do I need to invoke the balance method for this?
    {
        if (this.head == null) //'this' is the tree, check if empty
        {
            this.head = node; //set node as root of the tree
            //node.Parent = this.head; //its parent points to itself
            size++;
        }
           
        else
        {
            if (node.Parent == null)
                node.Parent = head; //start at head
            //Node is inserted on the left side if it is smaller or equal to the parent
            bool insertLeftSide = false;
            if (node.Value < node.Parent.Value)
            {
                insertLeftSide = true;
            }
            if (insertLeftSide) //insert on the left
            {
                if (node.Parent.LeftChild == null)
                {
                    node.Parent.LeftChild = node; //insert in left
                    size++;
                }
                else
                {
                    node.Parent = node.Parent.LeftChild; //scan down to left child
                    this.Add(node); //recursive call
                }
            }
            else //insert on the right
            {
                if (node.Parent.RightChild == null)
                {
                    node.Parent.RightChild = node; //insert in right
                    size++;
                }
                else
                {
                    node.Parent = node.Parent.RightChild;
                    this.Add(node);
                }
            }
        }
    }

    ///
    /// Returns the first node in the tree with the parameter value.
    ///
    public BinaryTreeNode Find(Int32 value)
    {
        BinaryTreeNode node = this.head; //start at head
        while (node != null)
        {
            if (node.Value.Equals(value)) //parameter value found
                return node;
            else
            {
                //Search left if the value is smaller than the current node
                bool searchLeft = false;
                if (node.Value > value)
                {
                    searchLeft = true;
                }
                if (searchLeft)
                    node = node.LeftChild; //search left
                else
                    node = node.RightChild; //search right
            }
        }
        return null; //not found
    }
    ///
    /// Removes a value from the tree and returns whether the removal was successful.
    ///
    public bool Remove(Int32 value)
    {
    BinaryTreeNode removeNode = Find(value);
    return this.Remove(removeNode);
    }
    ///
    /// Removes a node from the tree and returns whether the removal was successful.
    ///>
    ///
    public bool Remove(BinaryTreeNode removeNode)
    {
        if (removeNode == null)
            return false; //value doesn't exist or not of this tree
        //Note whether the node to be removed is the root of the tree
        bool wasHead = (removeNode == head);
        if (this.Count == 1)
        {
            this.head = null; //only element was the root
            size--; //decrease total element count
        }
        else if (removeNode.IsLeaf) //Case 1: No Children
        {
            //Remove node from its parent
            if (removeNode.IsLeftChild)
            {
                removeNode.Parent.LeftChild = null;
            }
            else
            {
                removeNode.Parent.RightChild = null;
            }
            removeNode.Parent = null;
            size--; //decrease total element count
        }
        else if (removeNode.ChildCount == 1) //Case 2: One Child
        {
            if (removeNode.HasLeftChild)
            {
                //Put left child node in place of the node to be removed
                removeNode.LeftChild.Parent = removeNode.Parent; //update parent
                if (wasHead)
                {
                    this.Root = removeNode.LeftChild; //update root reference if needed
                }
                if (removeNode.IsLeftChild) //update the parent's child reference
                {
                    removeNode.Parent.LeftChild = removeNode.LeftChild;
                }
                else
                {
                    removeNode.Parent.RightChild = removeNode.LeftChild;
                }
            }
            else //Has right child
            {
                //Put left node in place of the node to be removed
                removeNode.RightChild.Parent = removeNode.Parent; //update parent
                if (wasHead)
                {
                    this.Root = removeNode.RightChild; //update root reference if needed
                }
                if (removeNode.IsLeftChild) //update the parent's child reference
                {
                    removeNode.Parent.LeftChild = removeNode.RightChild;
                }
                else
                {
                    removeNode.Parent.RightChild = removeNode.RightChild;
                }
            }
            removeNode.Parent = null;
            removeNode.LeftChild = null;
            removeNode.RightChild = null;
            size--; //decrease total element count
        }
        else //Case 3: Two Children
        {
            //Find inorder predecessor (right‐most node in left subtree)
            BinaryTreeNode successorNode = removeNode.LeftChild;
            while (successorNode.RightChild != null)
            {
                successorNode = successorNode.RightChild;
            }
            removeNode.Value = successorNode.Value; //replace value
            this.Remove(successorNode); //recursively remove the inorder predecessor
        }
        return true;
    }

    //-----------------------------------
    // balancing the binary tree
    // after the tree has been built
    //
    // WARNING! This code has not been checked...
    // and you may need to change it
    // depending on your tree design
    //------------------------------------
    public void balance(BinaryTreeNode node)
    {
        if (node != null)
        {
            BinaryTree tree = new BinaryTree();
            if (node.RightChild.level - node.LeftChild.level > 1)
            {
                if (node.RightChild.level > node.LeftChild.level)
                {
                    node = rotateL(node);
                    node = rotateR(node);
                }
                else
                {
                    node = rotateL(node);
                }
            }
            else
            {
                if (node.LeftChild.level > node.RightChild.level)
                {
                    node = rotateR(node);
                    node = rotateL(node);
                }
                else
                {
                    node = rotateR(node);
                }
            }
            balance(node.LeftChild);
            balance(node.RightChild);
        }
    }
    // depth from node to left
    public int heightL(BinaryTreeNode node)
    {
        if (node == null)
            return 0;
        return node.LeftChild.level + 1;
    }
    // depth from node from the right
    public int heightR(BinaryTreeNode node)
    {
        if (node == null)
            return 0;
        return node.RightChild.level + 1;
    }
    // left rotation around node
    public BinaryTreeNode rotateL(BinaryTreeNode node)
    {
        if (node == null)
            return null;
        else
        {
            BinaryTreeNode newRoot = node.RightChild;
            node.RightChild = newRoot.leftChild;
            newRoot.leftChild = node;
            return newRoot;
        }
    }
    // right rotation around node
    public BinaryTreeNode rotateR(BinaryTreeNode node)
    {
        if (node == null)
            return null;
        else
        {
            BinaryTreeNode newRoot = node.LeftChild;
            node.LeftChild = newRoot.RightChild;
            newRoot.RightChild = node;
            return newRoot;
        }
    }


    //-------------------------------------
    // TraverseInOrder
    // Traverses the tree in this order:
    // Left, Root, Right
    // Calls the private function InOrder
    //-------------------------------------
    public void TraverseInOrder()
    {
        InOrder(ref head);
    }
    private void InOrder(ref BinaryTreeNode node)
    {
        balance(node); //Where I was attempting to balance before traversing which I think is what throws the error.
        if (node == null)
            return;
        if (node.LeftChild != null)
        {
            InOrder(ref node.leftChild);
        }
        Console.WriteLine(node.value);
        if (node.RightChild != null)
        {
            InOrder(ref node.rightChild);
        }
    }
    //-------------------------------------
    // TraversePreOrder
    // Traverses the tree in this order:
    // Root, Left, Right
    //-------------------------------------
    public void TraversePreOrder()
    {
        PreOrder(ref head);
    }
    private void PreOrder(ref BinaryTreeNode node)
    {
        if (node == null)
            return;

        Console.WriteLine(node.value);
        if (node.LeftChild != null)
        {
            InOrder(ref node.leftChild);
        }
        if (node.RightChild != null)
        {
            InOrder(ref node.rightChild);
        }
    }
    //-------------------------------------
    // TraversePostOrder
    // Traverses the tree in this order:
    // Left, Right, Root
    //-------------------------------------
    public void TraversePostOrder()
    {
        PostOrder(ref head);
    }
    private void PostOrder(ref BinaryTreeNode node)
    {
        if (node == null)
            return;
        if (node.LeftChild != null)
        {
            InOrder(ref node.leftChild);
        }
        if (node.RightChild != null)
        {
            InOrder(ref node.rightChild);
        }
        Console.WriteLine(node.value);
    }
}

BinaryTreeNode class:

//====================================================
//| Inspired by and Modified from: |
//| Visual C# Kicks ‐ http://www.vcskicks.com/ |
//| License ‐ http://www.vcskicks.com/license.html |
//====================================================
using System;
using System.Collections;
using System.Text;
namespace csKicksTreeApp
{
    ///
    /// A Binary Tree node that holds an element and references to other tree nodes
    ///
    /// Binary Tree Node class
    class BinaryTreeNode
    {
        public Int32 value;
        internal int level;
        public BinaryTreeNode leftChild;
        public BinaryTreeNode rightChild;
        public BinaryTreeNode parent;
      
        ///
        /// Creates a new instance of an empty node
        ///
        public BinaryTreeNode()
        {
            this.level = 0;
            this.parent = null;
            this.leftChild = null;
            this.rightChild = null;
            //deleted = null;
        }
        ///
        /// Create a new instance of a Binary Tree node
        ///
        public BinaryTreeNode(Int32 value)
        {
            this.level = 1;
            this.value = value;
            this.parent = null;
            this.leftChild = null;
            this.rightChild = null;
        }
        ///
        /// The value stored at the node
        ///
        public Int32 Value
        {
            get { return value; }
            set { this.value = value; }
        }
        ///
        /// Gets or sets the left child node
        ///
        public BinaryTreeNode LeftChild
        {
            get { return leftChild; }
            set { leftChild = value; }
        }
        ///
        /// Gets or sets the right child node
        ///
        public BinaryTreeNode RightChild
        {
            get { return rightChild; }
            set { rightChild = value; }
        }
        ///
        /// Gets or sets the parent node
        ///
        public BinaryTreeNode Parent
        {
            get { return parent; }
            set { parent = value; }
        }
        ///
        /// Gets whether the node is a leaf (has no children)
        ///
        public bool IsLeaf
        {
            get { return this.ChildCount == 0; }
        }
        ///
        /// Gets whether the node is internal (has children nodes)
        ///
        public bool IsInternal
        {
            get { return this.ChildCount > 0; }
        }
        ///
        /// Gets whether the node is the left child of its parent
        ///
        public virtual bool IsLeftChild
        {
            get { return this.Parent != null && this.Parent.LeftChild == this; }
        }
        ///
        /// Gets whether the node is the right child of its parent
        ///
        public virtual bool IsRightChild
        {
            get { return this.Parent != null && this.Parent.RightChild == this; }
        }
        ///
        /// Gets the number of children this node has
        ///
        public int ChildCount
        {
            get
            {
                int count = 0;
                if (this.LeftChild != null)
                    count++;
                if (this.RightChild != null)
                    count++;
                return count;
            }
        }
        ///
        /// Gets whether the current node has a left child node
        ///
        public bool HasLeftChild
        {
            get { return (this.LeftChild != null); }
        }
        ///
        /// Gets whether the current node has a right child node
        ///
        public bool HasRightChild
        {
            get { return (this.RightChild != null); }
        }
    }
}// end of binary tree node class

And finally my program:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace csKicksTreeApp
{
    class Program
    {

        static void Main(string[] args)
        {
            string input;
            int value;

            bool flag = true;

            while (flag)
            {
                try
                {

                    Random randomGenerator = new Random();

                    generate myRand = new generate(randomGenerator);

                    BinaryTree tree = new BinaryTree();

                    Console.WriteLine("Welcome to the Binary Search Tree.\n");
                    Options:
                    Console.WriteLine("\nWhat would you like to do?\nPress \"I\" to insert a node.\nPress \"D\" to delete a node.\nPress \"A\" to traverse in-order.\nPress \"B\" to traverse pre-order.\nPress \"C\" to traverse post-order.\nPress \"E\" to end the program.\n");
                    input = Console.ReadLine();

                    if (input == "i" || input == "I")
                    {
                        Console.WriteLine("\nPress \"I\" again if you would like to input your own value or any other key to input a random number.");
                        input = Console.ReadLine();

                        if (input == "i" || input == "I")
                        {
                            Console.WriteLine("\nPlease enter the value you would like to insert and press enter");
                            value = Convert.ToInt32(Console.ReadLine());
                        }

                        else
                        {
                            Console.WriteLine("\nGenerating random number...");
                            value = myRand.GetRandom();
                        }

                        tree.Add(value);
                       // rootNode = tree.Root;

                        Console.WriteLine("The value {0} was entered into the Tree.\n", value);

                        goto Options;
                    }
                    else if (input == "d" || input == "D")
                    {
                        Console.WriteLine("\nPlease enter the value you would like removing\n");
                        value =Convert.ToInt32(Console.ReadLine());

                        tree.Remove(value);

                        Console.WriteLine("The value {0} was removed from the Tree.\n", value);
                        
                        Console.WriteLine("\nPress any key to return to the options.\n");
                        Console.ReadLine();
                        goto Options;
                    }
                    else if (input == "a" || input == "A")
                    {
                        Console.WriteLine("\nBelow are the contents of the Binary Search Tree, shown In Order. Press any key to return to Options.\n");
                        tree.TraverseInOrder();
                        Console.ReadLine();
                        goto Options;
                    }
                    else if (input == "b" || input == "B")
                    {
                        Console.WriteLine("\nBelow are the contents of the Binary Search Tree, shown Pre Order. Press any key to return to Options.\n");
                        tree.TraversePreOrder();
                        Console.ReadLine();
                        goto Options;
                    }
                    else if (input == "c" || input == "C")
                    {
                        Console.WriteLine("\nBelow are the contents of the Binary Search Tree, shown Post Order. Press any key to return to Options.\n");
                        tree.TraversePostOrder();
                        Console.ReadLine();
                        goto Options;
                    }
                    else if (input == "e" || input == "E")
                    {
                        goto End;
                    }
                    else
                    {
                        Console.WriteLine("\nInvalid command. Please choose one of the options listed.");
                        Console.ReadLine();
                        goto Options;
                    }

                    End:
                    Console.WriteLine("\nWould you like to exit or restart the program? Press \"E\" again to exit, \"R\" to  restart or \"C\" to cancel.\n");
                    string newop = Console.ReadLine();

                    flag = false;

                    if (newop == "r" || newop == "R")
                    {
                        flag = true;
                        Console.WriteLine();
                    }

                    else if (newop == "c" || newop == "C")
                    {
                        goto Options;
                    }

                }
                catch (FormatException e)
                {
                    Console.WriteLine(e.Message);
                }
                catch (OutOfMemoryException e)
                {
                    Console.WriteLine(e.Message);
                }
                catch (Exception e)
                {
                    Console.WriteLine(e.Message);
                }
            }
        }
    }

    class generate
    {
        private Random _randomGenerator;
        private int _maxResult = 100;

        public int maxResult
        {
            get
            {
                return _maxResult;
            }

        }

        public generate()
        {
            throw new Exception("Needs a random object to be passed");
        }

        public generate(Random randomGenerator)
        {
            //Initialise the random number generator
            _randomGenerator = randomGenerator;
           
        }

        private int _generateRandom()
        {
            return _randomGenerator.Next(1, _maxResult + 1);
        }

        public int GetRandom()
        {
            return _generateRandom();
        }
    }
}

I've included all the code because i'm a beginner and have no idea where the problems may lie in the code. Any help would be greatly appreciated.

Thank you!

Edited 5 Years Ago by AdmiralDonkey: Adding comments

Object reference not set to an instance of an object

Cold you point out where that error in your code occured?

Cold you point out where that error in your code occured?

Hi,

The code compiles fine, I get the message during run of the program. Everything works fine until I attempt to press "A", "B", or "C" to use any of the traversal methods. This message then comes up in command line and takes me back to the main options of the program.

I tried to invoke the balance method in my first traversal method (TraverseInOrder) to attempt balancing before the traversal, which I think may be the reason this message is coming up - When I remove this the traversals run but not as intended as I can't figure out how to balance the contents of the tree before traversing.

Sorry if that didn't really help!

Edit: I edited the code with a comment where I tried to invoke it.

Edited 5 Years Ago by AdmiralDonkey: n/a

Did you know that VS has a fantastic debugger?

That's what I'm using to test the program when working with the code - that's what I meant by compiles ok because it doesn't throw any errors and runs ok, sorry I guess I shouldn't have said it runs ok with the VS debugger rather than compiles - wasn't sure if the debugger compiles when it runs!

Thanks for your replies btw!

The problem is in your Balance routine. It's not :)

I don't have time right now to fully debug it, but if you haven't solved it, I'll take a look at it later.

Just FYI, it seems it's always going to line 249 in the Balance routine. I haven't confirmed that it *always* does, but for all the values I've tried it has.

Ok, I've looked at it some more and you never change the level value of a node, it's always 1. This causes it to always go to line 249 where you rotate the tree even though it doesn't need rotating (if the child node levels are the same you don't need to rebalance).

You need to rethink this routine.

Ok, I've looked at it some more and you never change the level value of a node, it's always 1. This causes it to always go to line 249 where you rotate the tree even though it doesn't need rotating (if the child node levels are the same you don't need to rebalance).

You need to rethink this routine.

Hi Momerath, thanks very much for your help.

I'm still very confused about this - I thought maybe taking a break from it and coming back would help me figure it out but didn't quite work!

Do you think changing the if statements in the balance routine from .level to .value (eg node.RightChild.level to node.RightChild.value)? Seems taking a break from it has just made me forget what could work with it :(

I also tried changing the level values of the child nodes in the add rotuine but wasn't sure if this was correct (shown below)

public void Add(BinaryTreeNode node)
    {
        if (this.head == null) //'this' is the tree, check if empty
        {
            this.head = node; //set node as root of the tree
            //node.Parent = this.head; //its parent points to itself
            size++;
        }
           
        else
        {
            if (node.Parent == null)
                node.Parent = head; //start at head
            //Node is inserted on the left side if it is smaller or equal to the parent
            bool insertLeftSide = false;
            if (node.Value < node.Parent.Value)
            {
                insertLeftSide = true;
                //heightL(node);     <---------- HERE
            }
            if (insertLeftSide) //insert on the left
            {
                if (node.Parent.LeftChild == null)
                {
                    node.Parent.LeftChild = node; //insert in left
                    size++;
                }
                else
                {
                    node.Parent = node.Parent.LeftChild; //scan down to left child
                    this.Add(node); //recursive call
                }
            }
            else //insert on the right
            {
                //heightR(node);    <---------- HERE

                if (node.Parent.RightChild == null)
                {
                    node.Parent.RightChild = node; //insert in right
                    size++;
                }
                else
                {
                    node.Parent = node.Parent.RightChild;
                    this.Add(node);
                }
            }
        }
    }

The other main problem I have is I can't test if the balance routine is working as I have no idea how or where I need to call it (does ths need to be called in the traversal functions or in my program class, how and where?)

Sorry for all these questions but I really am stuck and it's been driving me insane!!

Many thanks.

This article has been dead for over six months. Start a new discussion instead.