Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor of two given nodes in the tree. The lowest common ancestor is defined as the lowest node that has both given nodes as descendants, where a node can be a descendant of itself.

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.
View editorial solution
Saving… · 11 lines
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right

class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:


Console

Click Run to execute sample tests.