You are given the root of a Binary Search Tree (BST) and an integer level.
The root node is at level 0. Each level represents the distance from the root.
Return the median value of all node values present at the given level. If the level does not exist or contains no nodes, return -1.
The median is defined as the middle element after sorting the values at that level in non-decreasing order. If the number of values at that level is even, return the upper median (the larger of the two middle elements after sorting).
Example 1:
Input: root = [4,null,5,null,7], level = 2
Output: 7
Explanation:
The nodes at level = 2 are [7]. The median value is 7.
Example 2:
Input: root = [6,3,8], level = 1
Output: 8
Explanation:
The nodes at level = 1 are [3, 8]. There are two possible median values, so the larger one 8 is the answer.
Example 3:
Input: root = [2,1], level = 2
Output: -1
Explanation:
There is no node present at level = 2, so the answer is -1.
Constraints:
[1, 2 * 105].1 <= Node.val <= 1060 <= level <= 2 * 105We notice that the problem requires us to find the median of node values at a certain level in a binary search tree. Since the definition of median is to sort the node values and take the middle value, and the in-order traversal of a binary search tree is inherently sorted, we can collect the node values at the specified level through in-order traversal.
We define a helper function dfs(root, i), where root is the current node and i is the level of the current node. In the function, if the current node is empty, we return directly. Otherwise, we recursively traverse the left subtree, check if the level of the current node equals the target level, and if so, add the value of the current node to the result list, and finally recursively traverse the right subtree.
We initialize an empty list nums to store the node values at the specified level, and call dfs(root, 0) to start the traversal. Finally, we check if nums is empty, and if so, return -1, otherwise return the value at the middle position of nums.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes in the tree.
Java
C++
Go
TypeScript
Practice Median of a Binary Search Tree Level with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor