129. Find the Lowest Common Ancestor of Two Nodes in a BST

Given a binary search tree and two values p and q that both exist in it, find their lowest common ancestor and print its value. 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). p and q are given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the two values p and q. Output: Print a single integer - the value of the lowest common ancestor of p and q.

1 <= number of nodes <= 10^5

This technique relies ENTIRELY on the BST ordering property - it would give wrong answers on a general (non-BST) binary tree, where value comparisons carry no directional meaning.

Given a binary SEARCH tree and two values, find their lowest common ancestor - using the tree's sorted-order property to skip searching irrelevant branches entirely. Brute force: Use the general binary-tree LCA algorithm (searching both subtrees recursively without using the sorted-order property) - this still works correctly, but examines more of the tree than necessary given the extra BST structure available. Optimised: The BST's ordering property lets you decide which single direction to search using just a value comparison, with NO need to explore both subtrees at any step - this turns an O(n) worst-case general search into an O(h) search bounded by the tree's height, dramatically faster on a balanced tree.

Walk from the root just once: at each node, if both p and q are smaller than the current node's value, move left; if both are larger, move right; otherwise (the current node's value sits between p and q, or equals one of them) the current node is the LCA and you can stop immediately. This finds the LCA without ever computing or storing either path explicitly, needing only O(h) steps and O(1) extra space, compared to the O(h) space the path-based approach still requires. Time: O(h) Space: O(1)

Treat the tree as an arbitrary binary tree (ignoring the BST ordering property): search for p and q separately using a generic traversal (DFS/BFS) that records the full path of nodes from the root to each target, then walk both recorded paths together from the start and return the last node at which they still agree before diverging. This works on any binary tree, but finding each path this way can require visiting the entire tree in the worst case, and both full paths must be stored. Time: O(n) Space: O(n)

Exploit the BST ordering to find each path directly instead of searching blindly: starting at the root, repeatedly compare the target value to the current node and move left or right accordingly, recording each node visited, until the target is found. Do this once for p and once for q, then compare the two recorded paths to find where they last agree. Using BST comparisons instead of a generic traversal shrinks each path-finding step from O(n) to O(h), though both full paths are still stored for the comparison step. Time: O(h) Space: O(h)

1. Start at the root. If both p and q are SMALLER than the current node's value, the LCA must be in the left subtree - move left. 2. If both are LARGER, the LCA must be in the right subtree - move right. 3. The moment p and q fall on different sides (or the current node equals one of them), that node is the LCA.

Time: O(h), where h is the tree's height - O(log n) for a balanced BST, O(n) in the worst case of a fully skewed one. Space: O(1) if done iteratively (just walking down with a loop), or O(h) if done recursively.

Test with p or q equal to the root, p and q both on the same side of the tree versus on opposite sides, and a tree with 10^5 nodes for performance.

Be ready to explain precisely why this BST-specific approach is faster than the general binary-tree LCA algorithm - the key is that value comparisons let you SKIP one entire subtree at each step, rather than needing to search both.