data_structures.binary_tree.lowest_common_ancestor

Functions

breadth_first_search(→ tuple[list[int], list[list[int]]])	sets every nodes direct parent
create_sparse(→ list[list[int]])	creating sparse table which saves each nodes 2^i-th parent
lowest_common_ancestor(→ int)
main(→ None)
swap(→ tuple[int, int])	Return a tuple (b, a) when given two integers a and b

Module Contents

data_structures.binary_tree.lowest_common_ancestor.breadth_first_search(level: list[int], parent: list[list[int]], max_node: int, graph: dict[int, list[int]], root: int = 1) → tuple[list[int], list[list[int]]]

sets every nodes direct parent parent of root node is set to 0 calculates depth of each node from root node

data_structures.binary_tree.lowest_common_ancestor.create_sparse(max_node: int, parent: list[list[int]]) → list[list[int]]

creating sparse table which saves each nodes 2^i-th parent

data_structures.binary_tree.lowest_common_ancestor.lowest_common_ancestor(u: int, v: int, level: list[int], parent: list[list[int]]) → int

data_structures.binary_tree.lowest_common_ancestor.main() → None

data_structures.binary_tree.lowest_common_ancestor.swap(a: int, b: int) → tuple[int, int]

Return a tuple (b, a) when given two integers a and b >>> swap(2,3) (3, 2) >>> swap(3,4) (4, 3) >>> swap(67, 12) (12, 67)