Skip to main content
Talentd

Median of a Binary Search Tree Level - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBreadth-First SearchBinary Search Tree11 min read
Practice this problem

Problem Statement

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:

  • The number of nodes in the tree is in the range [1, 2 * 105].
  • 1 <= Node.val <= 106
  • 0 <= level <= 2 * 10​​​​​​​5

Approach Overview

Problem 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.

Solution

We 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Level Collection + SortingO(n log w)O(n)Simplest implementation; good when level sizes are small or sorting cost is acceptable
DFS with Two Heaps per LevelO(n log w)O(n)Better when levels can be large and you want incremental median calculation without sorting

Video Solution

leetcode 3831 Median of a Binary Search Tree Level | recursion and bst specific solutions • Code-Yao • 27 views views

Frequently Asked Questions

Is Median of a Binary Search Tree Level easy or hard?
The problem is typically rated Medium. Traversing the tree is straightforward, but correctly organizing values by level and computing medians efficiently requires understanding of DFS, level grouping, and median calculation.
Median of a Binary Search Tree Level Python/Java solution
Most implementations use DFS where the function receives the current node and depth. Values are appended to a list for that depth, then medians are computed from those lists. The same logic works across Python, Java, C++, Go, and TypeScript.
How to solve Median of a Binary Search Tree Level in O(n)?
Pure O(n) time is difficult if you sort values at each level. A practical optimization is maintaining two heaps per level while traversing with DFS. Each insertion costs O(log w), giving O(n log w) overall while avoiding repeated sorting.
What is the best approach for Median of a Binary Search Tree Level?
A depth-first search that groups node values by level is the most common approach. During traversal, store values in arrays keyed by depth and compute the median for each level after traversal. This solution runs in O(n log w) time where w is the maximum width of the tree and uses O(n) space.
Is Median of a Binary Search Tree Level asked at Google/Amazon/Meta?
Tree traversal and level aggregation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving medians, averages, or statistics per level test knowledge of DFS, BFS, and data structure design.
What data structure is used in Median of a Binary Search Tree Level?
The core data structures are recursion or a stack for DFS traversal, a hash map or array keyed by depth to store level data, and optionally two heaps (max-heap and min-heap) to maintain medians efficiently.
What is the time complexity of Median of a Binary Search Tree Level?
The typical solution runs in O(n log w) time. DFS visits each of the n nodes once, and computing medians requires sorting or heap operations based on the number of nodes at each level, where w represents the maximum level width.

Ready to solve this problem?

Practice Median of a Binary Search Tree Level with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II