118. Lowest Common Ancestor in a Binary Tree

Given a binary tree and two values p and q that are both guaranteed to exist in it, find their lowest common ancestor - the deepest node that has both p and q in its subtree (a node can be its own ancestor). Print that node's 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 as two more integers after the tree's tokens.

Input: First line contains space-separated level-order tokens describing the binary tree ('N' marks an absent child). Second line contains the two integers 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 general technique works even without any ordering property (unlike the BST version) because it doesn't rely on comparing VALUES to decide direction - it purely tracks which subtree(s) successfully contain the targets.

Given two values known to exist in a binary tree, find the deepest node that is an ancestor of both. Brute force: Find the full root-to-p path and the full root-to-q path separately, then compare them to find the last node where they agree - this works but requires storing two full paths, more bookkeeping than the elegant recursive approach. Optimised: The recursive approach cleverly combines 'search' and 'identify the LCA' into a SINGLE traversal: a node discovers it's the LCA the moment its two child searches return DIFFERENT non-null findings, with no need to build or compare explicit path lists.

Find the root-to-p path and the root-to-q path separately, each as a list of nodes (one O(n) traversal per path). Then walk both lists together from the start - the last node where they still match, right before they diverge, is the LCA. Time: O(n) Space: O(n) - both full paths are stored

Recurse into the left and right subtrees looking for p and q at the same time. If the current node IS p or q, return it immediately. If both the left and right recursive calls come back non-null, p and q were found on different sides, so the current node is the LCA. Otherwise, pass along whichever side actually found something. This finds the answer in a single pass, with no explicit path ever stored. Time: O(n) Space: O(h) recursion stack only - no extra storage

For every node in the tree, check whether p and q are BOTH present in that nodes subtree (a simple recursive "does this subtree contain value x" helper). The deepest node for which this is true is the LCA. Since both subtrees are re-scanned from scratch at every single node, large parts of the tree get revisited many times over. Time: O(n^2) Space: O(h) recursion stack (h = height of tree)

1. Recursively search both the left and right subtrees for p and q. 2. If p or q equals the current node, or if p and q are each found in DIFFERENT subtrees of the current node, then the current node IS the LCA. 3. Otherwise, the LCA lies entirely within whichever single subtree successfully found something.

Time: O(n) in the worst case - each node's subtree may need to be searched once. Space: O(h) for the recursion stack, where h is the tree's height.

Test with a single-node tree (p and q both the root), p or q equal to the root (a node can be its own ancestor), and a tree at the maximum size of 10^5 nodes for performance.

Be ready to contrast this general binary-tree approach with the much simpler BST-specific LCA algorithm (which uses value comparisons to skip searching irrelevant subtrees entirely) - knowing both, and why the BST version is faster, is a great signal.