Median of BST — Solution in Python, Java & C++
Median of BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.
Median of BST is a medium coding problem on depth-first search and trees, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary search tree with n distinct values, return the median of its values.
With the values in increasing order, the median is the middle value when n is odd (the (n + 1) / 2-th value), and the average of the two middle values (the n / 2-th and (n / 2 + 1)-th) when n is even.
Return it as a string: an integer median is written plainly ("5"), and a median halfway between two integers is written with .5 ("3.5").
Example 1
Input: root = [6,3,8,1,4,7,9]
Output: 6
Explanation: Seven values 1, 3, 4, 6, 7, 8, 9: the middle one is 6.
Example 2
Input: root = [6,3,8,1,4,7]
Output: 5
Explanation: Six values 1, 3, 4, 6, 7, 8: the median is (4 + 6) / 2 = 5.
Example 3
Input: root = [5,2,9,1]
Output: 3.5
Explanation: Four values 1, 2, 5, 9: (2 + 5) / 2 = 3.5.
Constraints
1 <= number of nodes <= 10^41 <= Node.val <= 10^5all node values are distinct
Follow-up: Can you do it with O(1) extra space (no array of values, no recursion stack)?
Hints for Median of BST
Hint 1
An in-order traversal of a BST visits its values in increasing order — the k-th value visited is the k-th smallest.
Hint 2
Count the nodes first, then traverse again and stop at the middle one (or the middle two).
Hint 3
For O(1) extra space, use Morris traversal (temporarily threading each node's in-order predecessor to it) for both passes. An average of two integers is either an integer or ends in .5.
How to solve Median of BST
The median of a BST is a position in its in-order sequence. Count the nodes, then walk in order to the middle position(s); Morris traversal does both walks without a stack.
Approach
- Count the nodes,
n. - Traverse in order, numbering the visited values from 1.
- If
nis odd, the answer is the value numbered(n + 1) / 2. - If
nis even, take the values numberedn / 2andn / 2 + 1, add them tos; the answer iss / 2ifsis even, otherwise(s - 1) / 2followed by.5.
Why it works
In-order traversal of a BST lists the values sorted, so the value at position k is the k-th smallest and the median definition applies directly. The sum of two integers is even or odd, so their half is an integer or an integer plus one half — the string form is exact.
Complexity
- Time —
O(n) - Space —
O(h) with a recursive or stack-based traversal; O(1) with Morris traversal
Pitfalls
- Integer division of an odd sum drops the half — build the
.5explicitly. - The positions are 1-based in the definition; off-by-one here returns a neighbour of the median.
Reference solution
Python
from typing import Optional
def findMedian(root: Optional[TreeNode]) -> str:
vals = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
vals.append(node.val)
node = node.right
n = len(vals)
if n % 2 == 1:
return str(vals[n // 2])
s = vals[n // 2 - 1] + vals[n // 2]
return str(s // 2) if s % 2 == 0 else str(s // 2) + ".5"Java
public static String findMedian(TreeNode root) {
List<Integer> vals = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
vals.add(node.val);
node = node.right;
}
int n = vals.size();
if (n % 2 == 1) return String.valueOf(vals.get(n / 2));
int s = vals.get(n / 2 - 1) + vals.get(n / 2);
return s % 2 == 0 ? String.valueOf(s / 2) : (s / 2) + ".5";
}C++
string findMedian(TreeNode* root) {
vector<int> vals;
vector<TreeNode*> stack;
TreeNode* node = root;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back();
stack.pop_back();
vals.push_back(node->val);
node = node->right;
}
int n = (int) vals.size();
if (n % 2 == 1) return to_string(vals[n / 2]);
int s = vals[n / 2 - 1] + vals[n / 2];
return s % 2 == 0 ? to_string(s / 2) : to_string(s / 2) + ".5";
}JavaScript
var findMedian = function(root) {
var vals = [], stack = [], node = root;
while (stack.length > 0 || node !== null) {
while (node !== null) { stack.push(node); node = node.left; }
node = stack.pop();
vals.push(node.val);
node = node.right;
}
var n = vals.length;
if (n % 2 === 1) return String(vals[(n - 1) / 2]);
var s = vals[n / 2 - 1] + vals[n / 2];
return s % 2 === 0 ? String(s / 2) : String((s - 1) / 2) + ".5";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals