2476. Closest Nodes Queries in a Binary Search Tree | Leetcode discuss

Here is the link. 

C# | First try | Timeout on 34/35 | Search a BST

jianminchen

781

0

a few seconds ago

C#

Intuition

I was so naive to write a C# solution to search a binary search tree, and then the solution failed on test case 34/35. I could not figure out what is the reason, BST search is O(N), not log(N) for test case 34.

Approach

Complexity

• Time complexity:

• Space complexity:

Code

The following C# code failed test case 34/35.

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
public class Solution {
     /// <summary>
        /// Nov. 8, 2023
        /// Avoid unbalanced tree - O(N) - tree height is same as O(N), N total number of nodes in the tree
        /// Save binary tree in a sorted array first, and then apply binary search. 
        /// 
        /// </summary>
        /// <param name="root"></param>
        /// <param name="queries"></param>
        /// <returns></returns>
        public IList<IList<int>> ClosestNodes(TreeNode root, IList<int> queries)
        {
            var sorted = new List<int>();
            applyInOrder(root, sorted);

            var result = new List<IList<int>>();
            if (root == null)
            {
                return result; 
            }

            foreach (var number in queries)
            {
                var found = sorted.BinarySearch(number);

                if (found > -1)
                {
                    result.Add(new int[] { sorted[found], sorted[found] });
                }
                else
                {
                    var index = ~found;
                    var smallestLarger = -1;
                    var largestSmaller = -1;
                    if (index < sorted.Count)
                    {
                        smallestLarger = sorted[index];
                        if (index > 0)
                        {
                            largestSmaller = sorted[index - 1];
                        }
                    }
                    else
                    {
                        largestSmaller = sorted[sorted.Count - 1]; 
                    }

                    result.Add(new int[]{largestSmaller, smallestLarger}.ToList()); 
                }
            }

            return result;
        }

        private void applyInOrder(TreeNode root, IList<int> list)
        {
            if (root == null)
            {
                return; 
            }

            applyInOrder(root.left, list);
            
            list.Add(root.val);

            applyInOrder(root.right, list);
        }
}