< Back





236. Lowest Common Ancestor of a Binary Tree

Given the root of a binary tree and two nodes, p and q, we're asked to determine their
lowest common ancestor. The
lowest common ancestor can be either p or q, or some node in between.

We conduct a depth-first search to search for the two nodes, p and q. If we encounter either p or q,
we return the node. While search, if a particular path never sees p or q, None will propagate up the
tree as we backtrack. Eventually, we encounter a node where the left and right nodes are not None,
meaning that p and q are on different sides of the tree. This is the lowest common ancestor.

The solution is as follows:


  class Solution:
      def lowestCommonAncestor(
          self, root: TreeNode, p: TreeNode, q: TreeNode
      ) -> TreeNode:
          if not root:
              return None

          if root == p or root == q:
              return root

          left, right = self.lowestCommonAncestor(
              root.left, p, q
          ), self.lowestCommonAncestor(root.right, p, q)

          if left and right:
              return root

          if left:
              return left

          return right


_ Time Complexity:

  O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

  O(n) - We use recursion, so our call stack is size O(n).