Having issues with Binary Search Trees in C#

Question

I'm having a problem with the following code snippet:

using System;
using System.Collections.Generic;
using System.Text;

namespace trees_by_firas
{
    class Program
    {
        static void Main(string[] args)
        {
            BinarySearchTree t = new BinarySearchTree();

            t.insert(ref t.root, 10);
            t.insert(ref t.root, 5);
            t.insert(ref t.root, 6);
            t.insert(ref t.root, 17);
            t.insert(ref t.root, 2);
            t.insert(ref t.root, 3);

            BinarySearchTree.print(t.root);
            Console.WriteLine("--------------------");
            Console.WriteLine(t.FindMax());
            Console.WriteLine(t.FindMin());
            Console.WriteLine("--------------------");
            Console.WriteLine(t.CountLeaves());
            Console.WriteLine(t.CountNodes());



        }

        public class TreeNode
        {
            public int n;
            public TreeNode _left;
            public TreeNode _right;


            public TreeNode(int n, TreeNode _left, TreeNode _right)
            {
                this.n = n;
                this._left = _left;
                this._right = _right;
            }


            public void DisplayNode()
            {
                Console.Write(n);
            }


        }


        public class BinarySearchTree
        {
            public TreeNode root;


            public BinarySearchTree()
            {
                root = null;
            }


            public void insert(ref TreeNode root, int x)
            {
                if (root == null)
                {
                    root = new TreeNode(x, null, null);
                }
                else
                    if (x < root.n)
                        insert(ref root._left, x);
                    else
                        insert(ref root._right, x);
            }

            public int FindMin()
            {
                TreeNode current = root;

                while (current._left != null)
                    current = current._left;

                return current.n;
            }

            public int FindMax()
            {
                TreeNode current = root;

                while (current._right != null)
                    current = current._right;

                return current.n;
            }



            public TreeNode Find(int key)
            {
                TreeNode current = root;

                while (current.n != key)
                {
                    if (key < current.n)
                        current = current._left;
                    else
                        current = current._right;
                    if (current == null)
                        return null;
                }
                return current;
            }



            public void InOrder(ref TreeNode root)
            {
                if (root != null)
                {
                    InOrder(ref root._left);
                    root.DisplayNode();
                    InOrder(ref root._right);
                }
            }

            public int CountNodes()
            {
                int count = 1; // me!        
                if (root._left != null)
                    count += _left.CountNodes();
                if (root._right != null)
                    count += _right.CountNodes();
                return count;
            }

            public int CountLeaves()
            {
                int count = (root._left == null && root._right == null) ? 1 : 0;
                if (root._left != null)
                    count += _left.CountLeaves();
                if (root._right != null)
                    count += _right.CountLeaves();
                return count;
            }

            public static void print(TreeNode root)
            {
                if (root != null)
                {
                    print(root._left);
                    Console.WriteLine(root.n.ToString());
                    print(root._right);
                }

            }



        }

    }
}

---

I get the following errors:

Error 1 The name '_left' does not exist in the current context 

// on the countnodes & countleaves

Error 2 The name '_right' does not exist in the current context 
// on the countnodes & countleaves

Any thoughts on how I can fix these errors?

Answer 1

_left and _right are fields in TreeNode. You're trying to use them as if they're part of BinarySearchTree. I believe you can just prefix them with root.:

public int CountNodes()
{
    int count = 1; // me!        
    if (root._left != null)
        count += root._left.CountNodes();
    if (root._right != null)
        count += root._right.CountNodes();
    return count;
}

public int CountLeaves()
{
    int count = (root._left == null && root._right == null) ? 1 : 0;
    if (root._left != null)
        count += root._left.CountLeaves();
    if (root._right != null)
        count += root._right.CountLeaves();
    return count;
}

Answer 2

ok I fixed it but now I'm having logical error

public int CountNodes(TreeNode root)
            {
                int count = 1;
                if (root._left != null)
                    count += CountNodes(root._left);
                if (root._right != null)
                    count += CountNodes(root._right);
                return count;
            }

            public int CountLeaves(TreeNode root)
            {
                int count = (root._left == null && root._right == null) ? 1 : 0;
                if (root._left != null)
                    count += CountLeaves(root._left);
                if (root._right != null)
                    count += CountLeaves(root._right);
                return count;
            }

the output is 3 nodes and 6 leaves

thats wrong cuz the inserted numbers are 6 (check the main)

Answer 3

I get quite the opposite result from your code - 6 nodes and 3 leaves. 6 nodes is the number of items you have inserted into the tree, so this makes sense. The number of leaves should be the number of nodes in the tree having no children. As your tree currently looks like this...

     10
    /  \
   5   17
  / \
 2   6
  \
   3

...you have six nodes and three leaves (17,6 and 3).