Median of BST

Medium
1973.

Median of BST

Median of BST is a medium coding problem on depth-first search and trees, asked in Amazon interviews.

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^4
  • 1 <= Node.val <= 10^5
  • all node values are distinct

Follow-up: Can you do it with O(1) extra space (no array of values, no recursion stack)?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var findMedian = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= Node.val <= 10^5
  • all 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

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

  2. Hint 2

    Count the nodes first, then traverse again and stop at the middle one (or the middle two).

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

  1. Count the nodes, n.
  2. Traverse in order, numbering the visited values from 1.
  3. If n is odd, the answer is the value numbered (n + 1) / 2.
  4. If n is even, take the values numbered n / 2 and n / 2 + 1, add them to s; the answer is s / 2 if s is even, otherwise (s - 1) / 2 followed 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 .5 explicitly.
  • 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