Log inSign up
mediumGeeksforGeeksNot Started

Find Median of BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Binary Search Tree (BST) with N nodes, find the median of the BST.

The median is defined as: - If N is odd, the median is the value of the ((N + 1) / 2)-th node in the in-order traversal. - If N is even, the median is the average of the (N / 2)-th and ((N / 2) + 1)-th nodes in the in-order traversal: (val1 + val2) / 2.0.

You should aim for an optimal solution that uses O(1) auxiliary space without allocating extra arrays or recursion stack frames.

Constraints:

  • 1 <= N <= 105
  • 1 <= Node.data <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand median definition for odd and even number of tree nodes.
  • Implement Morris Traversal threading to traverse BST in O(1) space.
  • Combine two-pass counting with in-place pointer threading.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find median of Binary Search Tree.
  • Requirement of strictly O(1) auxiliary space (no recursion stack, no arrays).
  • Order statistics on threaded tree traversals.

Algorithmic Decision Tree:

  • If O(N) space allowed -> Inorder array collection.
  • If O(H) space allowed -> Two-pass recursive DFS.
  • If O(1) space required -> Two-pass Morris Traversal.

Connected Patterns:

Kth Smallest Element in a BSTBinary Tree Inorder TraversalMorris Inorder Traversal

1. Inorder Array Collection

Intuition

Perform a standard recursive inorder traversal, appending each visited node's data to a dynamic array or list. After visiting all N nodes, check if N is odd: return list[N / 2]. If N is even: return (list[N / 2 - 1] + list[N / 2]) / 2.0.

When to apply: When simplicity is paramount and O(N) space is permissible.

Algorithm

  1. Collect all node values in an array via standard inorder traversal and compute median from center elements.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct Node {
5 int data;
6 Node* left;
7 Node* right;
8 Node(int val) : data(val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(Node* root, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, vals);
15 vals.push_back(root->data);
16 inorder(root->right, vals);
17 }
18public:
19 double findMedian(Node* root) {
20 std::vector<int> vals;
21 inorder(root, vals);
22 int n = vals.size();
23 if (n == 0) return 0;
24 if (n % 2 != 0) {
25 return vals[n / 2];
26 } else {
27 return (vals[(n / 2) - 1] + vals[n / 2]) / 2.0;
28 }
29 }
30};
31
32int main() {
33 Node* root = new Node(6);
34 root->left = new Node(3);
35 root->right = new Node(8);
36 root->left->left = new Node(1);
37 root->left->right = new Node(4);
38 root->right->left = new Node(7);
39 root->right->right = new Node(9);
40
41 Solution sol;
42 std::cout << "Median: " << sol.findMedian(root) << std::endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N) auxiliary space

2. Two-Pass Recursive Inorder (O(H) Space)

Intuition

Pass 1: Count total nodes N using simple recursive tree size DFS. Pass 2: Run inorder traversal while maintaining a visited count. When count reaches N/2 (for even) or (N+1)/2 (for odd), record the values and terminate early.

When to apply: When O(H) recursion stack is allowed, avoiding full O(N) array allocation.

Algorithm

  1. Count total nodes in Pass 1; in Pass 2, traverse until reaching target indices, tracking previous and current nodes without storing the whole tree.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 int countNodes(Node* root) {
12 if (!root) return 0;
13 return 1 + countNodes(root->left) + countNodes(root->right);
14 }
15
16 void findTargetNodes(Node* root, int& currCount, int target1, int target2, int& val1, int& val2) {
17 if (!root) return;
18 findTargetNodes(root->left, currCount, target1, target2, val1, val2);
19
20 currCount++;
21 if (currCount == target1) val1 = root->data;
22 if (currCount == target2) val2 = root->data;
23
24 findTargetNodes(root->right, currCount, target1, target2, val1, val2);
25 }
26public:
27 double findMedian(Node* root) {
28 int n = countNodes(root);
29 if (n == 0) return 0;
30
31 int currCount = 0;
32 int val1 = -1, val2 = -1;
33 if (n % 2 != 0) {
34 findTargetNodes(root, currCount, (n + 1) / 2, -1, val1, val2);
35 return val1;
36 } else {
37 findTargetNodes(root, currCount, n / 2, (n / 2) + 1, val1, val2);
38 return (val1 + val2) / 2.0;
39 }
40 }
41};
42
43int main() {
44 Node* root = new Node(6);
45 root->left = new Node(3);
46 root->right = new Node(8);
47 root->left->left = new Node(1);
48 root->left->right = new Node(4);
49 root->right->left = new Node(7);
50 root->right->right = new Node(9);
51
52 Solution sol;
53 std::cout << "Median: " << sol.findMedian(root) << std::endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

3. Two-Pass Morris Inorder Traversal (O(1) Auxiliary Space)

Intuition

1. Pass 1: Run Morris Traversal to count total nodes N. When curr has no left child, increment count and move to curr.right. Otherwise, find inorder predecessor (pre = curr.left; while(pre.right && pre.right != curr) pre = pre.right). If pre.right == null, make thread pre.right = curr; curr = curr.left. If pre.right == curr, revert thread pre.right = null, increment count, and move to curr.right. 2. Pass 2: Run Morris Traversal again with a running count. Track prev and curr. When count == (N+1)/2 (for odd), return curr.data. When count == (N/2) + 1 (for even), average the saved prev.data and curr.data. 3. All threads are restored before returning, preserving the original tree structure.

When to apply: When strictly O(1) auxiliary space is mandated.

Algorithm

  1. Execute Morris Traversal twice: first pass counts N in O(1) space; second pass stops at median node(s) in O(1) space without recursion.

Morris Traversal Median Calculation Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Counts N = 7
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
Pass 1: Morris traversal visits all nodes without stack frames.
Decision / next transition
1
Why this step matters

Counts N = 7. Target index = (7 + 1) / 2 = 4.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 int countNodesMorris(Node* root) {
12 int count = 0;
13 Node* curr = root;
14 while (curr) {
15 if (!curr->left) {
16 count++;
17 curr = curr->right;
18 } else {
19 Node* pre = curr->left;
20 while (pre->right && pre->right != curr) {
21 pre = pre->right;
22 }
23 if (!pre->right) {
24 pre->right = curr;
25 curr = curr->left;
26 } else {
27 pre->right = nullptr;
28 count++;
29 curr = curr->right;
30 }
31 }
32 }
33 return count;
34 }
35public:
36 double findMedian(Node* root) {
37 if (!root) return 0;
38 int n = countNodesMorris(root);
39
40 int currCount = 0;
41 Node* prevNode = nullptr;
42 Node* curr = root;
43
44 int target1 = (n % 2 != 0) ? (n + 1) / 2 : (n / 2);
45 int target2 = (n % 2 != 0) ? -1 : (n / 2) + 1;
46
47 int val1 = -1, val2 = -1;
48
49 while (curr) {
50 if (!curr->left) {
51 currCount++;
52 if (currCount == target1) val1 = curr->data;
53 if (currCount == target2) val2 = curr->data;
54 prevNode = curr;
55 curr = curr->right;
56 } else {
57 Node* pre = curr->left;
58 while (pre->right && pre->right != curr) {
59 pre = pre->right;
60 }
61 if (!pre->right) {
62 pre->right = curr;
63 curr = curr->left;
64 } else {
65 pre->right = nullptr;
66 currCount++;
67 if (currCount == target1) val1 = curr->data;
68 if (currCount == target2) val2 = curr->data;
69 prevNode = curr;
70 curr = curr->right;
71 }
72 }
73 }
74
75 if (n % 2 != 0) return val1;
76 return (val1 + val2) / 2.0;
77 }
78};
79
80int main() {
81 Node* root = new Node(6);
82 root->left = new Node(3);
83 root->right = new Node(8);
84 root->left->left = new Node(1);
85 root->left->right = new Node(4);
86 root->right->left = new Node(7);
87 root->right->right = new Node(9);
88
89 Solution sol;
90 std::cout << "Median: " << sol.findMedian(root) << std::endl;
91 return 0;
92}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) strictly auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Inorder Array CollectionO(N)O(N) auxiliary spaceCollect all node values in an array via standard inorder traversal and compute median from center elements.O(N)
2.Two-Pass Recursive Inorder (O(H) Space)O(N)O(H) recursion stack spaceCount total nodes in Pass 1; in Pass 2, traverse until reaching target indices, tracking previous and current nodes without storing the whole tree.O(N)
3.Two-Pass Morris Inorder Traversal (O(1) Auxiliary Space)OptimalO(N)O(1) strictly auxiliary spaceExecute Morris Traversal twice: first pass counts N in O(1) space; second pass stops at median node(s) in O(1) space without recursion.O(N)

Common Pitfalls & Crucial Edge Cases

Returning integer division

Writing (val1 + val2) / 2 returns an integer, failing test cases that expect .5.

Corrupting tree with unremoved threads

Exiting loop before cleaning up pre.right threads.

Assuming BST is balanced

Assuming tree height is always O(log N) and using recursive stack space.

Crucial Edge Cases to Validate:

  • Single Node BST — N = 1, median is the root's value.
  • Two Node BST — N = 2, median is (node1.data + node2.data) / 2.0.
  • Completely Skewed BST (Linked list) — Morris traversal still runs in O(N) time and O(1) space without stack overflow.
  • Large values — Ensure sum val1 + val2 does not overflow 32-bit integer limits before floating division.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify early whether O(N) space or strictly O(1) space is expected.
  2. If interviewer asks for O(1) space, immediately name-drop Morris Inorder Traversal.
  3. Emphasize that the tree must be traversed completely in Pass 2 to remove all temporary threads and avoid tree corruption.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Morris Traversal require two passes to find the median of an arbitrary BST?

2.If N = 6 with sorted values [2, 4, 6, 8, 10, 12], what values determine the median?

3.Why is it dangerous to break out of a Morris traversal the instant the median is found?

Back to DSA Sheet