Comprehensive Implementation of a Binary Search Tree in C#, with explanations

BinarySearchTree.cs

using System;

namespace BinarySearchTree
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("\n\nCreate the BST! \n");
            var array = new int?[]{ 10, 5, 18, 5, 13, 20, null, 3, 5};
            TreeNode x = null;
            x = CreateBST(array, x);

            Console.WriteLine("\n\nSum of the BST! \n");
            int? sum = SumOfBST(x);
            Console.WriteLine("The sum is " + sum);

            Console.WriteLine("\n\nSum of the BST with a range! \n");
            int l = 5, r = 10;
            int sumInRange = SumOfBSTInRange(x, l, r);
            Console.WriteLine("The sum in the range [" + l + "," + r + "] is " + sumInRange);

            Console.WriteLine("\n\nSum of the BST leafs! \n");
            int sumOfLeafs = SumOfBSTLeafs(x);
            Console.WriteLine("The sum of the binary tree leafs is " + sumOfLeafs);

            Console.WriteLine("\n\nFinding a number in the BST! \n");
            int numberToFind = 5;
            int numberFrequency = FindNumberInNode(x, numberToFind);
            Console.WriteLine("The number " + numberToFind + " is the value of " + numberFrequency + " nodes in the Binary Search Tree" );
            
            Console.WriteLine("\n\nFinding height of the BST where first node is included in height! \n");
            Console.WriteLine("The height of the Binary Search Tree is " + HeightOfBSTMinus1(x));
            
            Console.WriteLine("\n\nFinding height of the BST! \n");
            Console.WriteLine("The height of the Binary Search Tree is " + HeightOfBST(x));
        }

        public static TreeNode CreateBST(int?[] arr, TreeNode x) // HERE, Function has to be static
        {
            for (int i = 0; i< arr.Length; i ++)
            {
                x = AddNode(x, arr[i]); // HERE
            }
            return x;
        }

        public static TreeNode AddNode(TreeNode x, int? i)
        {
            if (i == null)
                return x;
            if (x == null || x.value == null)
            {
                Console.WriteLine("Add node "+ i);
                return new TreeNode(i);
            }
            if (i >= x.value)
            {
                Console.WriteLine("Move to right of node " + x.value);
                x.right = AddNode(x.right, i); //HERE, node.RIGHT not just node
            }
            else if (i < x.value)
            {
                Console.WriteLine("Move to left of node " + x.value);
                x.left = AddNode(x.left, i); //HERE, node.LEFT not just node
            }
            return x; // HERE, don't return x above unless i is null
        }

        public class TreeNode
        {
            public int? value; // HERE, Protection level has to be public for the variables
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int? x)
            {
                value = x;
            }
        }

        public static int? SumOfBST(TreeNode x)
        {
            if (x == null || x.value == null)
                return 0;
            Console.WriteLine("Adding " + x.value);
            int? sum= x.value;
            if (x.right != null)
            {
                Console.WriteLine("Moving to the right of " + x.value);
                sum += SumOfBST(x.right);
            }
            if (x.left != null)
            {
                Console.WriteLine("Moving to the left of " + x.value);
                sum += SumOfBST(x.left);
            }
            return sum;
        }
        public static int SumOfBSTInRange(TreeNode x, int l, int r)
        {
            if (x == null || x.value == null)
                return 0;
            int sum = 0;
            if (x.value.Value >= l && x.value.Value <= r)
            {
                Console.WriteLine("Adding " + x.value);
                sum = x.value.Value;
            }
            if (x.right != null)
            {
                Console.WriteLine("Moving to the right of " + x.value);
                sum += SumOfBSTInRange(x.right, l, r);
            }
            if (x.left != null)
            {
                Console.WriteLine("Moving to the left of " + x.value);
                sum += SumOfBSTInRange(x.left, l, r);
            }
            return sum;
        }

        public static int SumOfBSTLeafs(TreeNode x)
        {
            if (x == null || x.value == null)
                return 0;
            int sum = 0;
            if (x.right == null & x.left == null)
            {
                Console.WriteLine("Adding " + x.value);
                sum = x.value.Value;
            }
            if (x.right != null)
            {
                Console.WriteLine("Moving to the right of " + x.value);
                sum += SumOfBSTLeafs(x.right);
            }
            if (x.left != null)
            {
                Console.WriteLine("Moving to the left of " + x.value);
                sum += SumOfBSTLeafs(x.left);
            }
            return sum;
        }

        public static int FindNumberInNode(TreeNode x, int number)
        {
            int frequency = 0;
            if (x == null || x.value == null)
                return 0;
            if (x.value.Value == number)
            {
                Console.WriteLine("Found " + number);
                frequency++;
            }
            if (x.right != null)
            {
                Console.WriteLine("Moving to the right of " + x.value);
                frequency += FindNumberInNode(x.right, number);
            }
            if (x.left != null)
            {
                Console.WriteLine("Moving to the left of " + x.value);
                frequency += FindNumberInNode(x.left, number);
            }
            return frequency;
        }
        
        public static int HeightOfBSTMinus1(TreeNode x)
        {
            int height = 0;
            if (x == null)
                return height;
            height = 1;
            if (x.right == null && x.left == null)
                return height;
            var heightRight = 0;
            var heightLeft = 0;
            // Get the maximum value of left and right nodes
            if (x.left != null)
                heightLeft += HeightOfBSTMinus1(x.left);
            if (x.right != null)
                heightRight += HeightOfBSTMinus1(x.right);
            height += Math.Max(heightRight, heightLeft);
            return height;
        }

        public static int HeightOfBST(TreeNode x)
        {
            int height = 0;
            if (x == null)
                return height;
            if (x.right == null && x.left == null)
                return height;
            else
                height++;
            var heightRight = 0;
            var heightLeft = 0;
            // Get the maximum value of left and right nodes
            if (x.left != null)
            {
                heightLeft += HeightOfBST(x.left);
            }
            if (x.right != null)
            {
                heightRight += HeightOfBST(x.right);
            }
            height += Math.Max(heightRight, heightLeft);
            return height;
        }
    }
}

Contains Binary Search Tree functions for Adding, Inserting, Searching, Finding the Height, Finding the Sum, etc.