Oct 30, 2022 · Oct 28, 2022 · Oct 28, 2022 · Oct 28, 2022 · Oct 28, 2022
diff --git a/Graphs/BinaryLifting.js b/Graphs/BinaryLifting.js
 * Tutorial on Binary Lifting: https://codeforces.com/blog/entry/100826
 */

 class BinaryLifting {
 exportclass BinaryLifting {
  constructor (root, tree) {
    this.root = root
    this.connections = new Map()
diff --git a/Graphs/LCABinaryLifting.js b/Graphs/LCABinaryLifting.js
 /**
 * Author: Adrito Mukherjee
 * Findind Lowest Common Ancestor By Binary Lifting implementation in JavaScript
 * The technique requires preprocessing the tree in O(N log N) using dynamic programming)
 * It can be used to find Lowest Common Ancestor of two nodes in O(log N)
 * Tutorial on Lowest Common Ancestor: https://www.geeksforgeeks.org/lca-in-a-tree-using-binary-lifting-technique
 */

 import { BinaryLifting } from './BinaryLifting'

 class LCABinaryLifting extends BinaryLifting {
  constructor (root, tree) {
    super(root, tree)
    this.depth = new Map() // depth[node] stores the depth of node from root
    this.depth.set(root, 1)
    this.dfsDepth(root, root)
  }

  dfsDepth (node, parent) {
    // DFS to find depth of every node in the tree
    for (const child of this.connections.get(node)) {
      if (child !== parent) {
        this.depth.set(child, this.depth.get(node) + 1)
        this.dfsDepth(child, node)
      }
    }
  }

  getLCA (node1, node2) {
    // We make sure that node1 is the deeper node among node1 and node2
    if (this.depth.get(node1) < this.depth.get(node2)) {
      [node1, node2] = [node2, node1]
    }
    // We check if node1 is the ancestor of node2, and if so, then return node1
    const k = this.depth.get(node1) - this.depth.get(node2)
    node1 = this.kthAncestor(node1, k)
    if (node1 === node2) {
      return node1
    }

    for (let i = this.log - 1; i >= 0; i--) {
      if (this.up.get(node1).get(i) !== this.up.get(node2).get(i)) {
        node1 = this.up.get(node1).get(i)
        node2 = this.up.get(node2).get(i)
      }
    }
    return this.up.get(node1).get(0)
  }
 }

 function lcaBinaryLifting (root, tree, queries) {
  const graphObject = new LCABinaryLifting(root, tree)
  const lowestCommonAncestors = []
  for (const [node1, node2] of queries) {
    const lca = graphObject.getLCA(node1, node2)
    lowestCommonAncestors.push(lca)
  }
  return lowestCommonAncestors
 }

 export default lcaBinaryLifting
diff --git a/Graphs/test/LCABinaryLifting.test.js b/Graphs/test/LCABinaryLifting.test.js
 import lcaBinaryLifting from '../LCABinaryLifting'

 // The graph for Test Case 1 looks like this:
 //
 //         0
 //        /|\
 //       / | \
 //      1  3  5
 //     / \     \
 //    2   4     6
 //         \
 //          7
 //         / \
 //        11  8
 //             \
 //              9
 //               \
 //                10

 test('Test case 1', () => {
  const root = 0
  const graph = [
    [0, 1],
    [0, 3],
    [0, 5],
    [5, 6],
    [1, 2],
    [1, 4],
    [4, 7],
    [7, 11],
    [7, 8],
    [8, 9],
    [9, 10]
  ]
  const queries = [
    [1, 3],
    [6, 5],
    [3, 6],
    [7, 10],
    [8, 10],
    [11, 2],
    [11, 10]
  ]
  const lowestCommonAncestors = lcaBinaryLifting(root, graph, queries)
  expect(lowestCommonAncestors).toEqual([0, 5, 0, 7, 8, 1, 7])
 })

 // The graph for Test Case 2 looks like this:
 //
 //         0
 //        / \
 //       1   2
 //      / \   \
 //     3   4   5
 //    /       / \
 //   6       7   8

 test('Test case 2', () => {
  const root = 0
  const graph = [
    [0, 1],
    [0, 2],
    [1, 3],
    [1, 4],
    [2, 5],
    [3, 6],
    [5, 7],
    [5, 8]
  ]
  const queries = [
    [1, 2],
    [3, 4],
    [5, 4],
    [6, 7],
    [6, 8],
    [7, 8]
  ]
  const lowestCommonAncestors = lcaBinaryLifting(root, graph, queries)
  expect(lowestCommonAncestors).toEqual([0, 1, 0, 0, 0, 5])
 })
Original file line number	Diff line number	Diff line change
Expand Up		@@ -9,7 +9,7 @@
		* Tutorial on Binary Lifting: https://codeforces.com/blog/entry/100826
		*/

		class BinaryLifting {
		exportclass BinaryLifting {
		constructor (root, tree) {
		this.root = root
		this.connections = new Map()
Expand Down
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,61 @@
		/**
		* Author: Adrito Mukherjee
		* Findind Lowest Common Ancestor By Binary Lifting implementation in JavaScript
		* The technique requires preprocessing the tree in O(N log N) using dynamic programming)
		* It can be used to find Lowest Common Ancestor of two nodes in O(log N)
		* Tutorial on Lowest Common Ancestor: https://www.geeksforgeeks.org/lca-in-a-tree-using-binary-lifting-technique
		*/

		import { BinaryLifting } from './BinaryLifting'

		class LCABinaryLifting extends BinaryLifting {
		constructor (root, tree) {
		super(root, tree)
		this.depth = new Map() // depth[node] stores the depth of node from root
		this.depth.set(root, 1)
		this.dfsDepth(root, root)
		}

		dfsDepth (node, parent) {
		// DFS to find depth of every node in the tree
		for (const child of this.connections.get(node)) {
		if (child !== parent) {
		this.depth.set(child, this.depth.get(node) + 1)
		this.dfsDepth(child, node)
		}
		}
		}

		getLCA (node1, node2) {
		// We make sure that node1 is the deeper node among node1 and node2
		if (this.depth.get(node1) < this.depth.get(node2)) {
		[node1, node2] = [node2, node1]
		}
		// We check if node1 is the ancestor of node2, and if so, then return node1
		const k = this.depth.get(node1) - this.depth.get(node2)
		node1 = this.kthAncestor(node1, k)
		if (node1 === node2) {
		return node1
		}

		for (let i = this.log - 1; i >= 0; i--) {
		if (this.up.get(node1).get(i) !== this.up.get(node2).get(i)) {
		node1 = this.up.get(node1).get(i)
		node2 = this.up.get(node2).get(i)
		}
		}
		return this.up.get(node1).get(0)
		}
		}

		function lcaBinaryLifting (root, tree, queries) {
		const graphObject = new LCABinaryLifting(root, tree)
		const lowestCommonAncestors = []
		for (const [node1, node2] of queries) {
		const lca = graphObject.getLCA(node1, node2)
		lowestCommonAncestors.push(lca)
		}
		return lowestCommonAncestors
		}

		export default lcaBinaryLifting
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,80 @@
		import lcaBinaryLifting from '../LCABinaryLifting'

		// The graph for Test Case 1 looks like this:
		//
		// 0
		// /\|\
		// / \| \
		// 1 3 5
		// / \ \
		// 2 4 6
		// \
		// 7
		// / \
		// 11 8
		// \
		// 9
		// \
		// 10

		test('Test case 1', () => {
		const root = 0
		const graph = [
		[0, 1],
		[0, 3],
		[0, 5],
		[5, 6],
		[1, 2],
		[1, 4],
		[4, 7],
		[7, 11],
		[7, 8],
		[8, 9],
		[9, 10]
		]
		const queries = [
		[1, 3],
		[6, 5],
		[3, 6],
		[7, 10],
		[8, 10],
		[11, 2],
		[11, 10]
		]
		const lowestCommonAncestors = lcaBinaryLifting(root, graph, queries)
		expect(lowestCommonAncestors).toEqual([0, 5, 0, 7, 8, 1, 7])
		})

		// The graph for Test Case 2 looks like this:
		//
		// 0
		// / \
		// 1 2
		// / \ \
		// 3 4 5
		// / / \
		// 6 7 8

		test('Test case 2', () => {
		const root = 0
		const graph = [
		[0, 1],
		[0, 2],
		[1, 3],
		[1, 4],
		[2, 5],
		[3, 6],
		[5, 7],
		[5, 8]
		]
		const queries = [
		[1, 2],
		[3, 4],
		[5, 4],
		[6, 7],
		[6, 8],
		[7, 8]
		]
		const lowestCommonAncestors = lcaBinaryLifting(root, graph, queries)
		expect(lowestCommonAncestors).toEqual([0, 1, 0, 0, 0, 5])
		})