1483. Kth Ancestor of a Tree Node

HardTreeDepth-First SearchBreadth-First SearchDesignBinary Search
Leetcode Link

Problem Description

In this problem, we are given a tree structure with n nodes that are numbered from 0 to n - 1. A tree is a hierarchical structure where each node can have one parent and potentially multiple children, but no cycles exist. The tree is defined through a parent array named parent, where parent[i] represents the parent of the ith node. The node with number 0 is the root of the tree and it does not have a parent. Our task is to determine the kth ancestor of a given node, where the kth ancestor is the kth node in the path from the given node to the root. To represent this tree structure and perform ancestry queries, we need to implement a TreeAncestor class with two methods:

  1. TreeAncestor(int n, int[] parent): Constructor method that initializes the tree with the number of nodes (n) and the parent array (parent).

  2. getKthAncestor(int node, int k): Method that returns the kth ancestor of the provided node (node). If the ancestor does not exist (i.e., the kth level ancestor is beyond the root), it should return -1.

Intuition

Finding the kth ancestor naively by following the parent pointers one by one can be very inefficient, especially when k is large. To optimize the query time, we can precompute some data that enables us to "jump" multiple nodes at once.

This optimization relies on the concept of "binary lifting", which essentially means that we can represent the jump of k nodes as a sum of powers of 2, since any number can be represented as a combination of powers of 2. With this idea, we can precompute for each node what the 1st, 2nd, 4th (... 2^i-th ...) ancestor is. We store this information in a two-dimensional list p, where p[i][j] represents the 2^j-th ancestor of node i.

The constructor method prepares the p table, where the first column (j = 0) is just the direct parent of each node. For larger jumps (when j > 0), we can find the 2^j-th ancestor by looking at the 2^(j-1)-th ancestor of the node that is already the 2^(j-1)-th ancestor of the current node -- effectively making a "double jump".

When we want to find the kth ancestor of a node, we look at the binary representation of k. For each bit that is set in k, we jump to an ancestor that is 2^i steps up from the current node, where i is the position of that bit. This method drastically reduces the number of steps needed to find the kth ancestor.

This binary lifting technique helps in reducing a potentially large number of steps to a manageable few, bounded by the number of bits used to represent the number k.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The solution uses a method called binary lifting to compute and query the kth ancestor of a node in a tree efficiently. Here is an in-depth explanation of how the algorithm works and the solution is implemented:

Data Structure Initialization

  • A 2D list self.p of size n x 18 is created to store the powers of two ancestors for each node.
    • Why 18? Because for the constraints generally found in such problems, 2^17 is usually enough to cover the height of any tree (since 2^17 is greater than 10^5, which is a common maximum limit for n).
    • self.p[i][j] holds the 2^j-th ancestor of node i. -1 is used to indicate that such an ancestor does not exist.
  • The __init__ method fills up the self.p matrix.
    • First, it copies the parent array to self.p[i][0] for all nodes because the 0-th power of 2 corresponds to immediate parents.
    • Then for each node i, it iterates over j from 1 to 17 (inclusive), using previously computed ancestors (from the j-1 step) to calculate the j-th power of 2 ancestor.
    • If at any point it encounters a -1, it implies that further ancestors do not exist, and it breaks from the inner loop.

Querying Ancestors

  • The getKthAncestor method computes the kth ancestor for a given node.
    • It loops through powers of two from 2^17 down to 2^0, examining the bits of k.
    • For each i in 17 down to 0, it checks if the i-th bit of k is set (k >> i & 1). If it is, it jumps to the ancestor that is 2^i steps up by accessing self.p[node][i].
    • If during this process the node becomes -1, the method breaks out of the loop, as it indicates that we have tried to query above the root Ancestor (above the height of the tree).
    • The method returns the current node after the loop ends, which represents the k-th ancestor if one exists, or -1 if it doesn't.

This solution efficiently calculates the k-th ancestor for any given node by making at most log(k) jumps, drastically reducing the time complexity compared to a naive approach which would potentially require k jumps.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's say we have a tree with 5 nodes where the parent array is [-1, 0, 0, 1, 2] and we want to find the Kth ancestor of node 4.

  1. First, we initialize the TreeAncestor class with n = 5 and the parent array. This initiates the data structure and computes all 2^i-th ancestors for each node.

  2. The initialization will produce a self.p table that might look something like this after computing the ancestors:

    1| Node | 1st(2^0) | 2nd(2^1) | 4th(2^2) | ... |
2|------|----------|----------|----------|-----|
3| 0    | -1       | -1       | -1       | ... |
4| 1    | 0        | -1       | -1       | ... |
5| 2    | 0        | -1       | -1       | ... |
6| 3    | 1        | 0        | -1       | ... |
7| 4    | 2        | 0        | -1       | ... |

  3. Now let's find the 2nd ancestor of node 4. We call getKthAncestor(4, 2).

  4. In binary, k = 2 is 10. This means we want to find the ancestor that is 2^1 (the second bit from right to left in the binary representation of k) steps up from our current node.

  5. We start from node 4 and check the highest power of two within 2, which is 2^1, and find the ancestor 2 steps up:

    • Access self.p[4][1], which gives us node 0 as the 2^1-th ancestor of node 4.

  6. Since there is no higher power of two within 2, we have reached our result. The 2nd ancestor of node 4 is node 0 as per our self.p table.

This walkthrough demonstrates how the binary lifting method is used to compute the kth ancestor of a node by looking up precomputed ancestors using binary steps, significantly reducing the number of computations needed.

Solution Implementation

1from typing import List
2
3class TreeAncestor:
4    def __init__(self, n: int, parent: List[int]):
5        # Create a list of lists to store the ancestors. The outer list has a length of n,
6        # and the inner lists have fixed length of 18 (assuming a ceiling of log2(n)).
7        self.ancestors = [[-1] * 18 for _ in range(n)]
8      
9        # Initialize the immediate ancestors from the parent array.
10        for i, direct_parent in enumerate(parent):
11            self.ancestors[i][0] = direct_parent
12      
13        # Precompute ancestors using dynamic programming.
14        # Iterate up to 2^17 (which covers all binary representations for k up to n).
15        for i in range(n):
16            for j in range(1, 18):
17                if self.ancestors[i][j - 1] == -1:
18                    continue  # There's no ancestor at this level, skip to the next
19                # Set the ancestor at the jth binary up-step to be the (j-1)th ancestor 
20                # of the (j-1)th ancestor of the current node.
21                self.ancestors[i][j] = self.ancestors[self.ancestors[i][j - 1]][j - 1]
22
23    def getKthAncestor(self, node: int, k: int) -> int:
24        # To find the kth ancestor, we look at the binary representation of k.
25        # We use bit manipulation to move upwards step by step.
26        for i in range(17, -1, -1):
27            # Check if the ith bit is set in the binary representation of k.
28            if k & (1 << i):
29                # Move up by 2^i ancestors.
30                node = self.ancestors[node][i]
31                # If there isn't an ancestor at this level, return -1.
32                if node == -1:
33                    break
34        return node
35
36# Usage example:
37# tree_ancestor = TreeAncestor(n, parent)
38# ancestor = tree_ancestor.getKthAncestor(node, k)
39
1class TreeAncestor {
2    // Sparse table to keep ancestors at power of two distance
3    private int[][] sparseTable;
4
5    // Constructor to initialize the sparse table with the direct parents provided
6    public TreeAncestor(int n, int[] parent) {
7        // Initialize sparse table, allowing us to jump up in powers of two
8        sparseTable = new int[n][18];
9        for (int[] row : sparseTable) {
10            Arrays.fill(row, -1); // Fill the table with -1 to indicate no ancestor
11        }
12        // Fill the first column of the sparse table with the given parents
13        for (int i = 0; i < n; ++i) {
14            sparseTable[i][0] = parent[i];
15        }
16        // Compute ancestors at 2^j distance for dynamic programming approach
17        for (int i = 0; i < n; ++i) {
18            for (int j = 1; j < 18; ++j) {
19                if (sparseTable[i][j - 1] != -1) { // If there is an ancestor at 2^(j-1) distance
20                    // Set the ancestor at 2^j distance by doubling the previous distance ancestor
21                    sparseTable[i][j] = sparseTable[sparseTable[i][j - 1]][j - 1];
22                }
23            }
24        }
25    }
26
27    // Returns the k-th ancestor of the node, or -1 if it does not exist
28    public int getKthAncestor(int node, int k) {
29        // Traverse bits of k in reverse order (start from highest bit)
30        for (int i = 17; i >= 0; --i) {
31            if (((k >> i) & 1) == 1) {
32                // If the ith bit is set, move up by 2^i in the tree
33                node = sparseTable[node][i];
34                // If there's no ancestor at this power of two, exit the loop early
35                if (node == -1) {
36                    break;
37                }
38            }
39        }
40        // Return the final ancestor, or -1 if not found
41        return node;
42    }
43}
44
45/**
46 * Your TreeAncestor object will be instantiated and called as such:
47 * TreeAncestor obj = new TreeAncestor(n, parent);
48 * int param_1 = obj.getKthAncestor(node, k);
49 */
50
1#include <vector>
2using namespace std;
3
4class TreeAncestor {
5public:
6    // Initialize the data structure with the number of nodes `n` and their direct parent array.
7    TreeAncestor(int n, vector<int>& parent) {
8        ancestors = vector<vector<int>>(n, vector<int>(MAX_POWER, -1));
9      
10        // Direct parent (1st ancestor) for each node.
11        for (int i = 0; i < n; ++i) {
12            ancestors[i][0] = parent[i];
13        }
14      
15        // Pre-compute all 2^j ancestors for each node where `j` ranges from 1 to MAX_POWER-1.
16        // This uses dynamic programming and the idea that the 2^j-th ancestor is the 2^(j-1)-th ancestor
17        // of the node's 2^(j-1)-th ancestor.
18        for (int i = 0; i < n; ++i) {
19            for (int j = 1; j < MAX_POWER; ++j) {
20                if (ancestors[i][j - 1] == -1) {
21                    continue; // If there is no ancestor, skip the computation.
22                }
23                ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
24            }
25        }
26    }
27
28    // Returns the k-th ancestor of the given node, or -1 if it does not exist.
29    int getKthAncestor(int node, int k) {
30        for (int i = MAX_POWER - 1; i >= 0; --i) {
31            if ((k >> i) & 1) { // Check each bit of `k`.
32                node = ancestors[node][i]; // Move up the tree by 2^i steps.
33                if (node == -1) {
34                    break; // If an ancestor does not exist at this level, return -1.
35                }
36            }
37        }
38        return node;
39    }
40
41private:
42    vector<vector<int>> ancestors; // 2D array where `ancestors[i][j]` is the 2^j-th ancestor of node `i`.
43    static const int MAX_POWER = 18; // The maximum power of 2 needed (2^17 covers more than 10^5 which is the typical constraint for node count).
44};
45
46
47/**
48 * Your TreeAncestor object will be instantiated and called as such:
49 * TreeAncestor* obj = new TreeAncestor(n, parent);
50 * int param_1 = obj->getKthAncestor(node,k);
51 */
52
1// Array to store preprocessed ancestor information.
2let precomputedAncestors: number[][];
3
4/**
5 * Function to initialize and preprocess the ancestor data.
6 * @param {number} size - The number of nodes in the tree.
7 * @param {number[]} parent - The array where the index represents the node and the value represents its parent.
8 */
9function initialize(size: number, parent: number[]): void {
10    // Initialize the precomputedAncestors array with dimensions 'size' x 18 and default value -1.
11    precomputedAncestors = new Array(size).fill(0).map(() => new Array(18).fill(-1));
12
13    // Populate the immediate parents of each node.
14    for (let i = 0; i < size; ++i) {
15        precomputedAncestors[i][0] = parent[i];
16    }
17
18    // Precompute ancestors for binary lifting.
19    for (let i = 0; i < size; ++i) {
20        for (let j = 1; j < 18; ++j) {
21            if (precomputedAncestors[i][j - 1] === -1) {
22                continue;
23            }
24            precomputedAncestors[i][j] = precomputedAncestors[precomputedAncestors[i][j - 1]][j - 1];
25        }
26    }
27}
28
29/**
30 * Function to find the k-th ancestor of a node using binary lifting.
31 * @param {number} node - The node for which the k-th ancestor is required.
32 * @param {number} k - The distance 'k' to the ancestor.
33 * @returns {number} - The node number of the k-th ancestor or -1 if it does not exist.
34 */
35function getKthAncestor(node: number, k: number): number {
36    // Traverse bits of 'k' from highest to lowest.
37    for (let i = 17; i >= 0; --i) {
38        // Check if the i-th bit is set in 'k'.
39        if (((k >> i) & 1) === 1) {
40            node = precomputedAncestors[node][i];
41
42            // If there is no ancestor at this distance, return -1.
43            if (node === -1) {
44                break;
45            }
46        }
47    }
48    // Return the final ancestor or -1 if not found.
49    return node;
50}
51
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which type of traversal does breadth first search do?

Time and Space Complexity

The given code defines a data structure for finding the k-th ancestor of a node in a tree with a pre-processing step that builds a sparse table for ancestor queries, and a query process that traverses this table to find the k-th ancestor.

Time Complexity

  • Pre-processing (__init__ method): The pre-processing step iterates over each of the n nodes and fills the sparse table called self.p. This table has 18 levels because 2^17 is the highest power of 2 that is below the potential maximum of n which may be up to 50000 (as per usual constraints on LeetCode problems) allowing us to reach any ancestor k < n with at most 17 jumps. Therefore, the time complexity for the pre-processing part is O(n * log n) since we have a nested loop where the outer loop runs for n and the inner loop for up to log n (which is 18 in this specific implementation assuming a reasonable upper bound for n).

  • Query (getKthAncestor method): For a single query to find the k-th ancestor, the method uses a loop that potentially iterates 18 times (the maximum number of jumps we need to make). For each iteration, it performs an O(1) check to see if the k-th ancestor exists for the current power of 2. Hence, the time complexity per query is O(log n).

Space Complexity

  • Pre-processing (__init__ method): The space complexity is O(n * logn). A sparse table (self.p) of size n x 18 is built, and each entry at self.p[i][j] represents the 2^j-th ancestor of node i. Since 18 is a constant which relates to the potential log n levels, the space complexity can be considered O(n * log n).

In conclusion, the pre-processing step has a time complexity of O(n * log n) and also a space complexity of O(n * log n). The query step has a time complexity of O(log n) per query. These complexities are assuming that bitwise operations and list indexing are O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ