Add solution #1483

JoshCrozier · JoshCrozier · commit 74cdddde4a04 · 2025-04-15T23:21:11.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,324 LeetCode solutions in JavaScript
+# 1,325 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1134,6 +1134,7 @@
 1480|[Running Sum of 1d Array](./solutions/1480-running-sum-of-1d-array.js)|Easy|
 1481|[Least Number of Unique Integers after K Removals](./solutions/1481-least-number-of-unique-integers-after-k-removals.js)|Medium|
 1482|[Minimum Number of Days to Make m Bouquets](./solutions/1482-minimum-number-of-days-to-make-m-bouquets.js)|Medium|
+1483|[Kth Ancestor of a Tree Node](./solutions/1483-kth-ancestor-of-a-tree-node.js)|Hard|
 1486|[XOR Operation in an Array](./solutions/1486-xor-operation-in-an-array.js)|Easy|
 1491|[Average Salary Excluding the Minimum and Maximum Salary](./solutions/1491-average-salary-excluding-the-minimum-and-maximum-salary.js)|Easy|
 1492|[The kth Factor of n](./solutions/1492-the-kth-factor-of-n.js)|Medium|
diff --git a/solutions/1483-kth-ancestor-of-a-tree-node.js b/solutions/1483-kth-ancestor-of-a-tree-node.js
@@ -0,0 +1,53 @@
+/**
+ * 1483. Kth Ancestor of a Tree Node
+ * https://leetcode.com/problems/kth-ancestor-of-a-tree-node/
+ * Difficulty: Hard
+ *
+ * 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 ith node. The root of the tree is node 0. Find the
+ * kth ancestor of a given node.
+ *
+ * The kth ancestor of a tree node is the kth 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 kth ancestor of the given node node. If there
+ *   is no such ancestor, return -1.
+ */
+
+/**
+ * @param {number} n
+ * @param {number[]} parent
+ */
+var TreeAncestor = function(n, parent) {
+  const maxDepth = Math.ceil(Math.log2(n));
+  this.ancestors = Array.from({ length: n }, () => new Array(maxDepth + 1).fill(-1));
+
+  for (let i = 0; i < n; i++) {
+    this.ancestors[i][0] = parent[i];
+  }
+
+  for (let j = 1; j <= maxDepth; j++) {
+    for (let i = 0; i < n; i++) {
+      if (this.ancestors[i][j - 1] !== -1) {
+        this.ancestors[i][j] = this.ancestors[this.ancestors[i][j - 1]][j - 1];
+      }
+    }
+  }
+};
+
+/**
+ * @param {number} node
+ * @param {number} k
+ * @return {number}
+ */
+TreeAncestor.prototype.getKthAncestor = function(node, k) {
+  let current = node;
+  for (let j = 0; k > 0 && current !== -1; j++, k >>= 1) {
+    if (k & 1) {
+      current = this.ancestors[current][j];
+    }
+  }
+  return current;
+};
