Algorithm Interview: Lowest Common Ancestor of 2 Nodes in Binary Tree

Hi, here's your problem today. This problem was recently asked by Apple:

You are given the root of a binary tree, along with two nodes, A and B. Find and return the lowest common ancestor of A and B. For this problem, you can assume that each node also has a pointer to its parent, along with its left and right child.

class TreeNode:

  def __init__(self, val):

    self.left = None

    self.right = None

    self.parent = None

    self.val = val



def lowestCommonAncestor(root, a, b):

  # Fill this in.



#   a

#  / \

# b   c

#    / \

#   d*  e*

root = TreeNode('a')

root.left = TreeNode('b')

root.left.parent = root

root.right = TreeNode('c')

root.right.parent = root

a = root.right.left = TreeNode('d')

root.right.left.parent = root.right

b = root.right.right = TreeNode('e')

root.right.right.parent = root.right



print lowestCommonAncestor(root, a, b).val

# c