424. Kth Ancestor of a Node in a Binary Tree

Given a binary tree, a node value, and an integer k, print the value of that node's kth ancestor (k=1 means its immediate parent), or -1 if no such ancestor exists (including when the node is the root). The node value and k are given on the next line after the tree.

Input: The first line contains space-separated level-order tokens ('N' for missing children) describing the binary tree. The second line contains two integers - the target node's value and k. Output: Print a single integer - the value of the target node's kth ancestor, or -1 if none exists.

1 <= number of nodes <= 10^5, 1 <= k <= number of nodes

The 'root is its own path of length 1' base case is what correctly produces -1 when k is large enough to go 'above' the root - the path-length check (k >= path length) cleanly handles this without needing a special separate check.

Given a node's value and a number k, find the value of the ancestor that's exactly k steps up from it (k=1 means its immediate parent). Brute force: Repeatedly walk UP from the target node using explicit parent pointers (if available) k times - this works directly if parent pointers exist, but plain binary trees given via level-order tokens typically don't have parent pointers readily available, making a root-to-node path search the more universally applicable approach. Optimised: A single DFS that builds the root-to-target path (appending to a list on the way down, removing on the way back up if the target isn't found in that branch) directly gives you random access to ANY ancestor by simple index arithmetic on the path list - no need to build or maintain explicit parent pointers throughout the whole tree.

Do a single DFS from the root that records the sequence of nodes visited on the way down; once the target value is found, the path from root to that node is exactly the list built so far. The kth ancestor is then just the element k positions before the end of that path (or -1 if the path isn't long enough). This directly matches the definition of 'ancestor' but requires storing the entire path explicitly, which can be as large as the whole tree for a skewed shape. Time: O(n) Space: O(n)

After building the parent map, precompute a sparse table up[node][j] representing the 2^j-th ancestor of each node, filled in using the recurrence up[node][j] = up[up[node][j-1]][j-1] for j from 1 up to log2(n). Answering a kth-ancestor query then means decomposing k into powers of two and hopping through the table in O(log n) instead of walking one parent link at a time. This costs more to build up front but makes each individual ancestor query dramatically cheaper, which pays off if many such queries need to be answered against the same tree. Time: O(n log n) Space: O(n log n)

Do one BFS or DFS pass over the whole tree to build a map from every node to its parent. Then, starting from the target node, walk up through the parent map exactly k times, stopping and returning -1 early if a null parent is reached before k steps are taken. This avoids storing a specific root-to-target path list and instead builds a reusable structure that would also let later ancestor queries on different nodes reuse the same map. Time: O(n) Space: O(n)

1. Find the full ROOT-TO-NODE path first, using a recursive search that records the path as it goes and backtracks (removes the last entry) whenever a branch doesn't lead to the target. 2. Once you have this path as a list ending in the target node, its kth ancestor is simply the entry EXACTLY k STEPS BEFORE THE END of that list. 3. If k is at least as large as the path's own length, no such ancestor exists (including when the target itself is the root) - print -1.

Time: O(n) in the worst case to find the root-to-node path (a skewed tree might require exploring most of it) - O(1) to then index into the kth ancestor once the path is known. Space: O(h), for storing the current path during the search.

Test k equal to or larger than the node's depth (prints -1), the target node being the root itself (also -1), k=1 (immediate parent), and n=10^5 nodes for performance.

Be ready to mention the alternative of pre-building explicit parent pointers for the WHOLE tree (via one initial traversal) if this exact QUERY needs to be answered repeatedly for MANY different nodes - amortizing the pointer-building cost across many queries.