Leetcode 315 - first time to practice, count of smaller number after self - could not pass the sample test case. Spent over one hour to write. Analysis is too weak to find the design issue.

Leetcode315_countOfSmallerNumbersAferSelf.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode315_countOfSmallerNumbersAfterSelf
{
    /// <summary>
    /// Leetcode 315 - 
    /// The code has a bug to count the value, could not pass the test case
    /// {5, 2, 6, 1}. 
    /// Need to figure out how to add the value to the node not on the path. 
    /// </summary>
    class Program
    {
        internal class Node
        {
            public int  Value;
            public Node Left;
            public Node Right;
            public int  Index { get; set; }
            public int  NumberNodeLessValue {get; set;}

            public Node(int number, int index)
            {
                Value = number; 
                Index = index;
            }
        }

        static void Main(string[] args)
        {
            var result = CountSmaller(new int[]{5, 2, 6, 1}); 
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static IList<int> CountSmaller(int[] numbers)
        {
            if(numbers == null || numbers.Length == 0)
            {
                return new List<int>(); 
            }

            var length = numbers.Length; 

            var result = new List<int>();             

            var root = new Node(numbers[0], 0);

            for (int index = 1; index < length; index++)
            {
                addToBinarySearchTree(root, numbers[index], index); 
            }

            var smaller = new int[length];
            traverseBST(root, smaller);

            return new List<int>(smaller);
        }

        private static void traverseBST(Node root, int[] smaller)
        {
            if(root == null)
            {
                return; 
            }

            smaller[root.Index] = root.NumberNodeLessValue;
            traverseBST(root.Left, smaller);
            traverseBST(root.Right, smaller);
        }

        /// <summary>
        /// Add new node to the binary search tree, and also keep the count of less value
        /// </summary>
        /// <param name="root"></param>
        /// <param name="newNode"></param>
        private static void addToBinarySearchTree(Node root, int newNode, int index)
        {
            //base case 
            var value     = root.Value;
            var isSmaller = newNode < value; 

            if(isSmaller)
            {
                // base case
                if(root.Left == null)
                {
                    root.NumberNodeLessValue++;
                    root.Left = new Node(newNode, index); 
                }
                else
                {
                    addToBinarySearchTree(root.Left, newNode, index); 
                }
            }
            else
            {
                if(root.Right == null)
                {
                    root.Right = new Node(newNode, index); 
                }
                else
                {
                    addToBinarySearchTree(root.Right, newNode, index); 
                }
            }
        }
    }
}