Find median of BST Hard 0 attempts
GeeksforGeeks ↗

Find median of BST

Hard TreeBinary TreeDFS GeeksforGeeks

You're given the root of a binary search tree. Find the median value among all the node values — if the tree holds an even number of nodes, the median is the average of the two values in the middle when sorted.

Input Format
Implement findMedian(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [6,3,8,1,4,7,9]
Output
6

Example 2

Input
root = [2,1]
Output
1.5
Constraints
  • 1 <= N <= 10^4
Test Cases (2)
Case 1
Args: [[6,3,8,1,4,7,9]] Expected: 6
Case 2
Args: [[2,1]] Expected: 1.5
Topics
TreeBinary TreeDFS

Iterative Inorder

Collect the sorted node values with an explicit stack. Return the middle value for an odd count or the average of the two middle values for an even count.

javascript
function findMedian(root) {
  const stack=[],values=[];let current=root;
  while(current||stack.length) {
    while(current){stack.push(current);current=current.left;}
    current=stack.pop();values.push(current.val);current=current.right;
  }
  const mid=Math.floor(values.length/2);
  return values.length%2 ? values[mid] : (values[mid-1]+values[mid])/2;
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript