Menu
I got asked this at a job interview. Here's my O(log n) solution.
Find the depth of the node.
Repeat the search, but stop at depth - n.
Is there a way to do this without the second pass?
707
Input the binary tree and the key_node whose ancestors are to be printed. Traverse all the nodes of the tree and perform recursive post order traversal. Until the key_node is found, traverse the left and right sub trees recursively. Once the key_node is reached, return the data of the nodes in the path.
3. How many ancestors does a node at level n in a binary tree have? Answer: 2^(h+1)-1-2^i . h=height of the tree.
A node that is connected to all lower-level nodes is called an "ancestor". The connected lower-level nodes are "descendants" of the ancestor node.
In your search for the node you can keep track of all nodes in the path from the current node to the root. This is a simple list with a length not greater than the depth of the tree. Once the node has been found, its nth ancestor is at position length - n in the list.
190
Your question is a bit wrong, I guess. You miss one important matter. Of course you can do it without second pass. Just maintain a queue of last n nodes in your search.
What you miss is that such algorithm needs O(log n) memory. While your solution trades off time consumption for memory usage, and uses O(1) (constant amount) of additional memory)
So your solution is not "wrong" or "too slow". It just has its own pros and cons.
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
