124. Insert a Node Into a Binary Search Tree

Given a binary search tree and a value to insert, insert it (as a new leaf, following BST ordering) and print the inorder traversal of the resulting tree, space-separated. 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). The value to insert is given on the next line.

Input: The first line contains space-separated level-order tokens ('N' for missing children) describing the BST. The second line contains a single integer - the value to insert. Output: Print the inorder traversal of the tree after insertion, space-separated on one line.

1 <= number of nodes <= 10^5

A new value ALWAYS attaches as a fresh leaf during simple BST insertion - it can never need to displace or rearrange any existing node, which is exactly why this operation is so cheap compared to deletion.

Add a new value into a BST as a new leaf, keeping the BST property intact. Brute force: Collect all values, add the new one, sort them all, and rebuild an entirely new tree from scratch - this works but discards the existing tree's structure and does far more work than a simple, targeted insertion. Optimised: Walking down using standard BST comparisons and attaching the new node at the first missing slot found modifies the EXISTING tree with a single O(h) walk - no rebuilding, no full traversal of the rest of the tree needed.

Perform the same BST-ordering comparisons as the recursive version, but using an explicit loop with a pointer walking down to the insertion spot instead of recursive calls, and print the result using an iterative inorder traversal (explicit stack, or Morris traversal for O(1) extra space). This produces the identical result as the recursive version but removes the reliance on the call stack, which matters because a skewed BST of up to 10^5 nodes could otherwise risk a stack overflow during recursive insertion or traversal. Time: O(h) insertion + O(n) traversal Space: O(1) extra (Morris) or O(h)

Since only the resulting inorder traversal is required (not the exact tree shape), collect all existing values via an inorder traversal into a sorted array, then insert the new value into its correct position in that array using a linear scan and print the array directly. This sidesteps the tree structure entirely and is easy to reason about, but it does unnecessary work shifting array elements and ignores the BST's actual pointer structure that the problem is really about. Time: O(n) Space: O(n)

Actually insert into the tree: starting at the root, recursively compare the value to insert against the current node - go left if smaller, right if larger or equal - until reaching a null child slot, where the new node is attached as a leaf. Then print the result with a standard recursive inorder traversal. This respects the real BST structure (which the array approach ignored) and only touches nodes along a single root-to-leaf path for the insertion itself, though the recursive calls consume stack space proportional to the tree's height. Time: O(h) insertion + O(n) traversal Space: O(h)

1. Walk down from the root: go left if the new value is smaller than the current node, right if larger. 2. Continue until you reach a MISSING child slot - that's exactly where the new node attaches. 3. Attach the new node there as a leaf.

Time: O(h), where h is the tree's height. Space: O(h) if implemented recursively, or O(1) extra if implemented iteratively.

Test inserting into a single-node tree, inserting a value smaller than every existing value and one larger than every existing value (attaches at an extreme end), and n=10^5 nodes for performance.

Be ready to note that since a BST's inorder traversal is always sorted, the FINAL answer (printing the inorder traversal after insertion) is simply the original sorted values plus the new one, re-sorted - a useful sanity check even if you're not asked to print the tree's actual shape.