How hard is LeetCode 1644. Lowest Common Ancestor of a Binary Tree II?

LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is rated Medium on LeetCode.

What is the time complexity of LeetCode 1644. Lowest Common Ancestor of a Binary Tree II?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 1644. Lowest Common Ancestor of a Binary Tree II?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 1644. Lowest Common Ancestor of a Binary Tree II cover?

LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is tagged Tree, Depth-First Search and Binary Tree on LeetCode.

Is LeetCode 1644. Lowest Common Ancestor of a Binary Tree II a premium problem?

Yes. LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Lowest Common Ancestor of a Binary Tree II — LeetCode 1644 Python Solution

MediumLeetCode PremiumTreeDepth-First SearchBinary Tree

Problem: #1644
Pattern: Tree Traversal
Reading time: 5 min
Source: leetcode.com

The problem

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null.

Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(
        self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
    ) -> 'TreeNode':
        def dfs(root, p, q):
            if root is None:
                return False
            l = dfs(root.left, p, q)
            r = dfs(root.right, p, q)
            nonlocal ans
            if l and r:
                ans = root
            if (l or r) and (root.val == p.val or root.val == q.val):
                ans = root
            return l or r or root.val == p.val or root.val == q.val

        ans = None
        dfs(root, p, q)
        return ans

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1644. Lowest Common Ancestor of a Binary Tree II?: LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is rated Medium on LeetCode.
What is the time complexity of LeetCode 1644. Lowest Common Ancestor of a Binary Tree II?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 1644. Lowest Common Ancestor of a Binary Tree II?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 1644. Lowest Common Ancestor of a Binary Tree II cover?: LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is tagged Tree, Depth-First Search and Binary Tree on LeetCode.
Is LeetCode 1644. Lowest Common Ancestor of a Binary Tree II a premium problem?: Yes. LeetCode 1644. Lowest Common Ancestor of a Binary Tree II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.