Kth Ancestor of a Tree Node

Hard

Asked by:

25 views

Topics:

TreesDynamic Programming

You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of i^th node. The root of the tree is node 0. Find the k^th ancestor of a given node.

The k^th ancestor of a tree node is the k^th node in the path from that node to the root node.

Implement the TreeAncestor class:

TreeAncestor(int n, int[] parent) Initializes the object with the number of nodes in the tree and the parent array.
int getKthAncestor(int node, int k) return the k^th ancestor of the given node node. If there is no such ancestor, return -1.

Example 1:

Input
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]
Output
[null, 1, 0, -1]

Explanation
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

Constraints:

1 <= k <= n <= 5 * 10⁴
parent.length == n
parent[0] == -1
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5 * 10⁴ queries.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

How is the tree represented (e.g., parent array, adjacency list, Node objects with parent pointers)?
What is the range of values for the node values, and is it possible for node values to be negative?
If the kth ancestor does not exist (e.g., k is larger than the depth of the node), what should I return (null, -1, or throw an exception)?
Is the value of 'k' guaranteed to be non-negative, and what is the maximum possible value of 'k'?
Is the input tree guaranteed to be a valid tree (e.g., no cycles, a single root node)?

Brute Force Solution

Approach

To find the Kth ancestor of a node, the most straightforward approach is to simply walk up the tree one step at a time. We essentially climb up the tree from the given node until we've moved 'K' steps upwards.

Here's how the algorithm would work step-by-step:

Start at the node we're given.
Move to its direct parent node.
Repeat the process of moving to the parent node. Count how many steps you've taken so far.
Keep moving to the parent node until you have climbed up exactly 'K' steps.
The node you are currently at after taking 'K' steps is the Kth ancestor.
If, at any point, you reach the very top of the tree (the root) before taking 'K' steps, it means the Kth ancestor doesn't exist and you would return nothing.

Code Implementation

def kth_ancestor_brute_force(node, k, parent_map):
    steps_taken = 0
    current_node = node

    # Traverse upwards until k steps are taken
    while steps_taken < k:
        # If we reach the root, the ancestor does not exist
        if current_node not in parent_map:
            return None

        current_node = parent_map[current_node]
        steps_taken += 1

    return current_node

Big(O) Analysis

Time Complexity

O(k) – The algorithm climbs up the tree from the given node to its ancestor. In the worst-case scenario, we have to traverse 'k' levels to find the Kth ancestor. Therefore, the time complexity is directly proportional to the value of 'k', representing the number of steps taken upwards. As the number of nodes in the tree (n) does not directly influence how many steps it takes to find the ancestor, the Big O notation depends on k. If k is large, it can approach n in the extreme case but the number of steps dominates the analysis.

Space Complexity

O(1) – The described iterative approach only requires a few integer variables to keep track of the current node and the number of steps taken. The space used by these variables remains constant regardless of the number of nodes, N, in the tree. There are no auxiliary data structures like arrays, lists, or hash maps created in this algorithm. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To efficiently find a node's ancestor that is 'k' levels above it in a tree, we use a precomputed table. This table allows us to jump up multiple levels at once, significantly reducing the number of steps compared to going up one level at a time.

Here's how the algorithm would work step-by-step:

First, prepare a table that tells you the ancestor at different levels of the tree, specifically powers of two (like 1, 2, 4, 8 levels above). This table is constructed by looking at each node and finding its immediate parent, its grandparent (2 levels up), its great-grandparent (4 levels up), and so on.
Once you have the table, to find the 'k'th ancestor, break down the number 'k' into a sum of powers of two. For example, if k is 5, you can break it down into 4 + 1.
Use the table to jump up the tree by the largest power of two that's less than or equal to 'k'. In the example above, you'd first jump up 4 levels.
Subtract that power of two from 'k', and repeat the process with the remaining value of 'k'. In the example, after jumping up 4 levels, you're left with 1, so you jump up 1 more level.
After these jumps, you will have reached the 'k'th ancestor of the starting node.

Code Implementation

class TreeAncestor:

    def __init__(self, number_of_nodes: int, parent: list[int]):
        self.max_jump = number_of_nodes.bit_length()
        self.ancestors = [([0] * number_of_nodes) for _ in range(self.max_jump)]

        # Initialize the first level of ancestors (immediate parents).
        for node in range(number_of_nodes):
            self.ancestors[0][node] = parent[node]

        # Build the ancestor table for higher powers of 2.
        for jump in range(1, self.max_jump):
            for node in range(number_of_nodes):
                intermediate_ancestor = self.ancestors[jump - 1][node]
                if intermediate_ancestor != -1:
                    self.ancestors[jump][node] = self.ancestors[jump - 1][intermediate_ancestor]
                else:
                    self.ancestors[jump][node] = -1

    def getKthAncestor(self, node: int, distance: int) -> int:
        # Iterate through the powers of 2 to find the kth ancestor.
        for jump in range(self.max_jump):
            # If the current power of 2 is needed to reach k.
            if (distance >> jump) & 1:
                node = self.ancestors[jump][node]

                # If we reach the root, return -1.
                if node == -1:
                    return -1

        return node

Big(O) Analysis

Time Complexity

O(n log n) – Building the ancestor table dominates the time complexity. For each of the n nodes in the tree, we iterate up to log n times to find ancestors at powers of two (1, 2, 4, 8,...). Finding the kth ancestor then involves iterating through the powers of two representation of k, which takes at most log k steps. Since k <= n (k is at most the height of the tree), log k <= log n. Therefore the overall time complexity is O(n log n) for precomputation and O(log n) for each ancestor query. If we only focus on the precomputation, which is often the case with this pattern, the complexity is O(n log n).

Space Complexity

O(N log N) – The dominant space complexity comes from the precomputed table used to store ancestors. This table has dimensions N x log(N), where N is the number of nodes in the tree. Each row represents a node, and each column represents the ancestor at a power of 2 level above that node (1, 2, 4, 8, etc.). Therefore, the space required to store this table is proportional to N * log(N). No other significant auxiliary space is used beyond this table.

Edge Cases

Case	How to Handle
Null or empty tree	Return null or appropriate error if the tree is null since there are no nodes to find ancestors of.
k is zero	Return the node itself as the 0th ancestor of a node is the node itself.
k is larger than the height of the tree from the given node	Return null because the node does not have a kth ancestor at this depth.
Node is null	Return null since there's no node to find ancestors of.
Node is the root, and k is greater than 0	Return null since the root has no ancestor.
k is a very large number, potentially leading to integer overflow if not handled carefully	Use a data type large enough to hold potential values of k, or implement a check to prevent arbitrarily large k.
Tree with only one node	If k > 0 return null since there are no ancestors, else if k = 0 return the node itself.
Skewed tree (e.g., a linked list)	The algorithm might need to traverse a long chain of nodes which could impact performance; consider binary lifting optimization.

Null or empty tree

How to Handle:

Return null or appropriate error if the tree is null since there are no nodes to find ancestors of.

k is zero

How to Handle:

Return the node itself as the 0th ancestor of a node is the node itself.

k is larger than the height of the tree from the given node

How to Handle:

Return null because the node does not have a kth ancestor at this depth.

Node is null

How to Handle:

Return null since there's no node to find ancestors of.

Node is the root, and k is greater than 0

How to Handle:

Return null since the root has no ancestor.

k is a very large number, potentially leading to integer overflow if not handled carefully

How to Handle:

Use a data type large enough to hold potential values of k, or implement a check to prevent arbitrarily large k.

Tree with only one node

How to Handle:

If k > 0 return null since there are no ancestors, else if k = 0 return the node itself.

Skewed tree (e.g., a linked list)

How to Handle:

The algorithm might need to traverse a long chain of nodes which could impact performance; consider binary lifting optimization.