Median of a BST in O(n) time, O(1) space / count nodes in a range

Medium

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 6

Example 2

Input:  count in [5, 45] for BST {10, 5, 50, 1, 40, 100}
Output: 3

Also 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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.