Lowest Common Ancestor

#138 · Trees · Advanced · 125 XP · about 20 min

In a binary tree, the lowest common ancestor of two nodes is the deepest node that has both of them in its subtree, where a node counts as part of its own subtree. Write common_ancestor(root, a, b) that returns the value of the lowest common ancestor of the nodes with values a and b. All values in the tree are different, and both a and b are in it. It is a plain binary tree, not a search tree, so the values are in no particular order.

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

        8
      /   \
     4     9
    / \     \
   1   6     2
      / \
     5   0

tree = build([8, 4, 9, 1, 6, None, 2, None, None, 5, 0])
common_ancestor(tree, 5, 0)  # returns 6
common_ancestor(tree, 1, 2)  # returns 8
common_ancestor(tree, 4, 0)  # returns 4

5 and 0 are both children of 6. The paths from the root to 1 and to 2 split at the root, 8. In the last example 0 sits below 4, so 4 is the answer.

Constraints

1 to 2,000 nodes with different integer values, which can be 0 or negative.
a and b are both in the tree, and they may be equal.

# Provided: do not change

from collections import deque

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

def build(values):

"""Build a tree from a level-order list; None marks a missing child."""

if not values or values[0] is None:

return None

root = Node(values[0])

queue = deque([root])

i = 1

while queue and i < len(values):

node = queue.popleft()

if values[i] is not None:

node.left = Node(values[i])

queue.append(node.left)

i += 1

if i < len(values) and values[i] is not None:

node.right = Node(values[i])

queue.append(node.right)

i += 1

return root

def common_ancestor(root, a, b):

# Your code here

pass

print(common_ancestor(build([8, 4, 9, 1, 6, None, 2, None, None, 5, 0]), 5, 0))

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.