Median of a BST in O(n) time, O(1) space / count nodes in a range
Problem
(1) Return the median of all values in a BST using O(n) time and O(1) extra space (no recursion stack, so use Morris traversal). (2) Count the nodes whose values lie in the range [low, high].
Example 1
Input: BST {1, 3, 4, 6, 7, 8, 9}
Output: median 6Example 2
Input: count in [5, 45] for BST {10, 5, 50, 1, 40, 100}
Output: 3Also asked as: Find the median of BST in O(n) time and O(1) space · Count BST ndoes that lie in a given range
Test cases
Case 1
Input: [10,5,50,1,null,40,100], 5, 45 Expected: 3
Case 2
Input: [10,5,50,1,null,40,100], 1, 100 Expected: 6
Case 3
Input: [10,5,50,1,null,40,100], 200, 300 Expected: 0
Case 4
Input: [], 1, 2 Expected: 0
View solutionHide solution1 approach
1. Morris in-order traversal (median) + pruned recursion (range count)
Time O(n)Space O(1) for median
Morris traversal walks in-order with O(1) space by temporarily threading predecessors. First pass counts n; second pass stops at position n/2. Range count: skip a subtree entirely when its root is outside [lo, hi].
function countInRange(node, lo, hi) { if (!node) return 0; if (node.val < lo) return countInRange(node.right, lo, hi); if (node.val > hi) return countInRange(node.left, lo, hi); return 1 + countInRange(node.left, lo, hi) + countInRange(node.right, lo, hi);}Morris median: do one Morris pass to count nodes, a second Morris pass to read the middle value(s). Threads are removed as you go, so no stack/recursion.