leetcode

commit 70e7750f0729ea05fdcf95dcc876e415c69ecbfa
parent d7a284890aaa5bb228ad65f09ad9d10181550485
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 21 Dec 2025 20:49:59 -0700

1483. kth ancestor of a tree node

Diffstat:
A
kth_ancestor_treenode.c
 | 
71
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
kth_ancestor_treenode.py
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 116 insertions(+), 0 deletions(-)
diff --git a/kth_ancestor_treenode.c b/kth_ancestor_treenode.c
@@ -0,0 +1,71 @@
+// 1483. Kth Ancestor of a Tree Node
+#include "leetcode.h"
+
+/*
+ * 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 the 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.
+ */
+
+typedef struct {
+  int **parents;
+} TreeAncestor;
+
+void build(TreeAncestor *obj, bool *built, int node) {
+  if (node == -1)
+    return;
+  if (built[node])
+    return;
+  for (int i = 1; i <= 20; ++i) {
+    int parent = obj->parents[node][i - 1];
+    if (parent == -1)
+      break;
+    if (!built[parent])
+      build(obj, built, parent);
+    obj->parents[node][i] = obj->parents[parent][i - 1];
+  }
+  built[node] = true;
+}
+
+TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize) {
+  TreeAncestor *obj = (TreeAncestor *)malloc(sizeof(TreeAncestor));
+  obj->parents = (int **)malloc(parentSize * sizeof(int *));
+  bool *built = (bool *)calloc(parentSize, sizeof(bool));
+  for (int i = 0; i < parentSize; ++i) {
+    obj->parents[i] = (int *)malloc(20 * sizeof(int));
+    memset(obj->parents[i], -1, 20 * sizeof(int));
+    obj->parents[i][0] = parent[i];
+  }
+  for (int i = 0; i < parentSize; ++i)
+    build(obj, built, i);
+  free(built);
+  return obj;
+}
+
+int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) {
+  if (!k)
+    return node;
+  if (node == -1)
+    return -1;
+  int tier = 0;
+  for (int i = 20; i >= 1; --i)
+    if ((1 << i) <= k) {
+      tier = i;
+      break;
+    }
+  return treeAncestorGetKthAncestor(obj, obj->parents[node][tier],
+                                    k - (1 << tier));
+}
+
+void treeAncestorFree(TreeAncestor *obj) { free(obj); }
+
+int main() {
+  int parent[] = {-1, 0, 0, 1, 1, 2, 2};
+  TreeAncestor *obj = treeAncestorCreate(7, parent, ARRAY_SIZE(parent));
+  printf("%d\n", treeAncestorGetKthAncestor(obj, 3, 1)); // expect: 1
+  printf("%d\n", treeAncestorGetKthAncestor(obj, 5, 2)); // expect: 0
+  printf("%d\n", treeAncestorGetKthAncestor(obj, 6, 3)); // expect: -1
+  treeAncestorFree(obj);
+}
diff --git a/kth_ancestor_treenode.py b/kth_ancestor_treenode.py
@@ -0,0 +1,45 @@
+# 1483. Kth Ancestor of a Tree Node
+from math import log2
+
+"""
+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 the 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.
+"""
+
+
+class TreeAncestor(object):
+    def __init__(self, n, parent):
+        """
+        :type n: int
+        :type parent: List[int]
+        """
+        m = int(log2(n)) + 1
+        self.dp = [[-1] * m for _ in range(n)]
+        for j in range(m):
+            for i in range(n):
+                if j == 0:
+                    self.dp[i][0] = parent[i]
+                elif self.dp[i][j - 1] != -1:
+                    self.dp[i][j] = self.dp[self.dp[i][j - 1]][j - 1]
+
+    def getKthAncestor(self, node, k):
+        """
+        :type node: int
+        :type k: int
+        :rtype: int
+        """
+        while k > 0 and node != -1:
+            i = int(log2(k))
+            node = self.dp[node][i]
+            k -= 1 << i
+        return node
+
+
+if __name__ == "__main__":
+    obj = TreeAncestor(n=7, parent=[-1, 0, 0, 1, 1, 2, 2])
+    print(obj.getKthAncestor(node=3, k=1))
+    print(obj.getKthAncestor(node=5, k=2))
+    print(obj.getKthAncestor(node=6, k=3))