SUM OF PREVIOUS SMALLER NUMBERS IN ARRAY

SUM OF PREVIOUS SMALLER NUMBERS IN ARRAY

//For every given element in the array you should return the sum of previous smaller values you //encountered in the array.

//In the solution here basically we are building a BST and every node in the tree would hold  
//the sum of all the node values towards its left (i.e. lesser than that node).
//To calculate sum of prev small numbers we add the 
//current node's value and current nodes sum to the sum being calculated.
namespace SumOfPrevSmallNumInArr
{
    class BST
    {
        class TreeNode
        {
            public int data;
            public TreeNode left;
            public TreeNode right;
            public int Sum; //for SumOfPrevSmallNumInArr

            public TreeNode(int val)
            {
                this.data = val;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }

            public TreeNode(int val, int index)
            {
                this.data = val;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }

            public TreeNode()
            {
                this.data = 0;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }
        }

        TreeNode Root;
        public BST()
        {
            Root = null;
        }

        public int AddNodeAndReturnSumOfPrevSmallNumInArr(int val)
        {
            TreeNode Node = new TreeNode(val);
            if (Root == null)
            {
                Root = Node;
                return 0;
            }

            TreeNode cur = Root;
            TreeNode Prev = null;
            int Sum = 0;

            while (cur != null)
            {
                Prev = cur;
                //If moving towards right add the current node's value and its 
                //sum value to the sum being calculated to return.
                if (val >= cur.data)
                {
                    Sum += cur.data + cur.Sum;
                    cur = cur.right;
                }
                //If moving towards left add the value to current node's sum.
                else
                {
                    cur.Sum += val;
                    cur = cur.left;
                }
            }
            if (val >= Prev.data) Prev.right = Node;
            else Prev.left = Node;
            return Sum;
        }

        
    }
    class Program
    {
        static void Main(string[] args)
        {
            int[] Arr = { 2, 3, 8, 6, 1 };

            //Sum of prev small numbers in arr
            BST BinSearchTree = new BST();
            for (int i = 0; i < Arr.Length; i++)
            {
                Console.WriteLine(BinSearchTree.AddNodeAndReturnSumOfPrevSmallNumInArr(Arr[i]));
            }

        }
    }
}