126. Find the Minimum and Maximum Value in a BST

Given a binary search tree, print its minimum value and its maximum value as 'min max'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens describing the BST ('N' marks an absent child). Output: Print the minimum and maximum values as 'min max' on one line.

1 <= number of nodes <= 10^5

This simple 'walk left/right to the end' technique is reused as a building block in several harder BST problems (like finding predecessors/successors), so it's worth having it feel completely automatic.

Find the smallest and largest values stored in a binary search tree. Brute force: Traverse the entire tree and track the smallest and largest values seen - this works but costs O(n), when the BST's structure lets you find both directly in O(h) without visiting most of the tree. Optimised: The BST property guarantees the minimum is always reachable by repeatedly going left from the root, and the maximum by repeatedly going right - no comparison against unrelated nodes is ever needed, since the ordering guarantees correctness of this simple directional walk.

Perform a single inorder traversal of the BST; because inorder traversal of a BST always visits nodes in ascending sorted order, the very first value produced is the minimum and the very last value produced is the maximum. This leverages the BST's ordering property (unlike the brute approach's generic node-by-node comparison) to identify the extremes directly from the traversal order, though it still visits every node to complete the traversal. Time: O(n) Space: O(h)

Exploit the BST invariant directly without visiting most of the tree at all: starting from the root, repeatedly step to the left child until there is none - that node holds the minimum value - and separately, starting from the root again, repeatedly step to the right child until there is none - that node holds the maximum. Each walk only touches nodes along a single path determined by the tree's height, so neither walk needs to look at the rest of the tree, making this the most direct algorithm possible for a BST. Time: O(h) Space: O(1)

Traverse the whole tree in any order (e.g. a simple recursive walk) and, for each node visited, compare its value against a running minimum and a running maximum seen so far, updating them as needed. This treats the tree as a generic binary tree and ignores the BST ordering property entirely, so it's correct for any tree shape, but it visits every single node even though a BST's structure would let the extremes be found much faster. Time: O(n) Space: O(h)

1. To find the minimum, start at the root and keep moving LEFT until there's no left child left - that final node holds the minimum. 2. To find the maximum, do the same but keep moving RIGHT instead.

Time: O(h), where h is the tree's height. Space: O(1) if done iteratively with a simple loop.

Test with a single-node tree (min equals max), a left-skewed tree, a right-skewed tree, and a tree with 10^5 nodes for performance.

This is a great warm-up question specifically testing whether you understand the BST invariant deeply enough to avoid an unnecessary full traversal.