1902. Depth of BST Given Insertion Order | Time out TLE 65/70

1902DepthOfBSTGivenInsertionOrder.cs

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

namespace _1902_depthBSTGivenInsertionOrder
{
    class Program
    {
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;

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

        static void Main(string[] args)
        {
            var test = new Program();
            var height = test.MaxDepthBST(new int[]{2, 1, 4, 3}); 
        }

        /// <summary>
        /// 1902 Depth of BST given insertion order 
        /// </summary>
        /// <param name="order"></param>
        /// <returns></returns>
        public int MaxDepthBST(int[] order)
        {
            if (order == null || order.Length == 0)
            {
                return 0; 
            }

            TreeNode newRoot = new TreeNode(order[0]);

            setupBST(order, ref newRoot, 1);

            // check BST's height
            return calculateHeight(newRoot); 
        }

        private int calculateHeight(TreeNode root)
        {
            if (root == null)
            {
                return 0; 
            }

            return 1 + Math.Max(calculateHeight(root.left), calculateHeight(root.right));
        }

        private void setupBST(int[] order, ref TreeNode root, int start)
        {
            if (start >= order.Length)
            {
                return; 
            }

            var visit = root; 
            var insert = order[start];

            while(true)
            {
                if (insert > visit.val)
                {
                    if (visit.right == null)
                    {
                        visit.right = new TreeNode(insert);
                        break;
                    }

                    visit = visit.right; 
                }
                else if (insert < visit.val)
                {
                    if (visit.left == null)
                    {
                        visit.left = new TreeNode(insert);
                        break; 
                    }

                    visit = visit.left; 
                }
            }

            setupBST(order, ref root, start + 1);
        }
    }
}