Watch the video solution for Median of a Binary Search Tree Level, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by Code-Yao has 26 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 105Problem Overview: Given the root of a binary search tree, compute the median value of node values at each depth level. Nodes on the same depth form a level; the task is to aggregate their values and return the median for each level.
Approach 1: DFS with Level Collection (O(n log w) time, O(n) space)
Traverse the tree using Depth-First Search. Pass the current depth during recursion and append each node value to a list associated with that level. After traversal, each level contains all its node values. Sort the list for that level and compute the median: the middle element for odd counts or the average of the two middle elements for even counts. Sorting each level costs O(k log k) where k is the level width, so the total complexity becomes O(n log w) where w is the maximum number of nodes on any level.
Approach 2: DFS with Two Heaps per Level (O(n log w) time, O(n) space)
Instead of storing and sorting full lists, maintain a streaming median structure for each depth using two heaps: a max‑heap for the lower half and a min‑heap for the upper half. During a DFS traversal of the Binary Tree, insert each node's value into the heap pair corresponding to its level and rebalance them so their sizes differ by at most one. The median is either the top of one heap or the average of both tops. This avoids sorting large arrays and keeps each insertion at O(log w).
Recommended for interviews: The DFS level-collection approach is the easiest to implement and clearly demonstrates tree traversal and level grouping. Interviewers often accept it first because the logic is straightforward. The heap-based approach shows stronger algorithmic thinking since you compute medians incrementally without sorting, which scales better when levels become large.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Level Collection + Sorting | O(n log w) | O(n) | Simplest implementation; good when level sizes are small or sorting cost is acceptable |
| DFS with Two Heaps per Level | O(n log w) | O(n) | Better when levels can be large and you want incremental median calculation without sorting |