The lowest common ancestor of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root.

Applications

Complexity

  • Time: Worst:
  • Space: Worst:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

    const G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
];

const T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child
  [-1, -1],
  [-1, 7],
  [-1, -1],
  [6, 1],
  [-1, -1],
  [3, 8],
  [0, 2],
  [-1, -1],
  [10, 4],
  [-1, -1],
  [9, -1],
];

function lcaBT(parent, root, a, b) {
  
  console.log(`Beginning new Iteration of lcaBT () with parent: ${parent}, current root: ${root}`);
  
  if (root === -1) {
    
    console.log('Reached end of path & target node(s) not found');
    
    return null;
  }

  }

  return (left !== null ? left : right);
}

const a = 7;
const b = 2;

console.log(`Lowest common ancestor of ${a} & ${b} is: ${lcaBT(null, 5, a, b)}`);