434. Find the Median of a BST

Given a binary search tree with n nodes, print its median value: if n is odd, print the single middle value of the sorted values; if n is even, print the average of the two middle values (guaranteed to be a whole number in every test case here).

Input: A single line of space-separated level-order tokens describing the BST ('N' marks an absent child). Output: Print a single integer - the median value of the BST.

1 <= number of nodes <= 10^5

This problem explicitly guarantees the even-case average is always a whole number in every test case - simplifying the output format, though in general median-of-two-values problems this guarantee wouldn't necessarily hold.

Find the middle value of a binary search tree's sorted values - a single middle value if there's an odd count, or the average of the two middle values if even. Brute force: Collect all values via inorder traversal into an array, then directly index into the middle position(s) - this works perfectly well and is simple; the only further optimization is avoiding building the full array. Optimised: For O(1) extra space, a Morris inorder traversal (which temporarily modifies the tree's structure using 'threading' to avoid needing a stack or recursion) can find the nth/2-th value directly without ever building an explicit array - a nice advanced optimization, though the array-based approach is simpler and fully correct for typical constraints.

Traverse the BST in some order that isn't guaranteed to be sorted (e.g. level order or preorder), collect all n values into an array, then sort that array from scratch and read off the middle element(s) by index. This is correct because sorting any collection of the values yields the true sorted order, but it completely ignores that a BST's inorder traversal is already sorted, paying an unnecessary O(n log n) sorting cost. Time: O(n log n) Space: O(n)

Perform an inorder traversal (left, node, right) of the BST, appending each visited value to an array; by the BST property, this array comes out already sorted with no further sorting needed. Then read the middle element (odd n) or average the two middle elements (even n) directly by index. This removes the wasted sort of the brute-force approach, dropping the time to linear, though it still uses O(n) auxiliary space to hold the array. Time: O(n) Space: O(n)

First, do one traversal (or use a size field, if maintained) purely to count n, so the target index/indices for the median are known in advance. Then perform an inorder Morris traversal - which uses temporary threaded links through the tree's own null pointers instead of a stack or array - stopping to record values only when the traversal reaches the target index/indices, and skipping the rest. This finds the median in the same linear time as storing a full array, but drops auxiliary space to O(1) since no array or explicit stack is ever built. Time: O(n) Space: O(1)

1. Perform an inorder traversal - for a BST, this visits values in ascending sorted order automatically. 2. If there are n values total and n is odd, the median is the value at position n/2 (0-indexed, integer division). 3. If n is even, the median is the average of the values at positions (n/2 - 1) and (n/2).

Time: O(n) - one inorder traversal to collect (or directly count/index into) the sorted values. Space: O(n) for the array-based approach, or O(1) with the more advanced Morris traversal technique.

Test with an odd node count (single middle value), an even node count (average of the two middle values), a single-node tree, and a tree with 10^5 nodes for performance.

Be ready to state the exact index formulas for odd versus even counts precisely - a small but easy place to make an off-by-one error under pressure.