Binary Tree

Question 1

Lowest Common Ancestor of nodes

Answer 1

def lca(root, nodes):
    if root is None: return None
    if root in nodes: return root
    left_lca = lca(root.left, nodes)
    right_lca = lca(root.right, nodes)
    if left_lca is None: return right_lca
    if right_lca is None: return left_lca
    return root

Question 2

BFS (pre-order traversal) of binary tree

Answer 2

row = [root]
while row:
row = [child for n in row for child in (n.left, n.right) if child]