(node, k)
| 54 | } |
| 55 | |
| 56 | kthAncestor(node, k) { |
| 57 | // if value of k is more than or equal to the number of total nodes, we return the root of the graph |
| 58 | if (k >= this.connections.size) { |
| 59 | return this.root |
| 60 | } |
| 61 | // if i-th bit is set in the binary representation of k, we jump from a node to its 2^i-th ancestor |
| 62 | // so after checking all bits of k, we will have made jumps of total length k, in just log k steps |
| 63 | for (let i = 0; i < this.log; i++) { |
| 64 | if (k & (1 << i)) { |
| 65 | node = this.up.get(node).get(i) |
| 66 | } |
| 67 | } |
| 68 | return node |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | function binaryLifting(root, tree, queries) { |
no test coverage detected