Coding - Lowest Common Ancestor of a Binary Tree

Here is the full interview question "Coding - Lowest Common Ancestor of a Binary Tree" asked at Uber:

Problem Statement: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on LeetCode, the lowest common ancestor of two nodes p and q is the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Examples:

1. Given binary tree: 3,5,1,6,2,0,8,#,#,7,4, and nodes p = 5 and q = 1. 3 / \ 5 1 / \ / \ 6 2 0 8 Return the LCA of nodes 5 and 1, which is 3.

2. Given binary tree: 3,5,1,6,2,0,8,#,#,7,4, and nodes p = 5 and q = 4. 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 Return the LCA of nodes 5 and 4, which is 1.

3. Given binary tree: 1,2, and nodes p = 2 and q = 2. 1 \ 2 Return the LCA of nodes 2 and 2, which is 2.

Constraints:

• The number of nodes in the tree is in the range [2, 10^4].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• The p and q values are different and non-null.

Hints:

1. Use recursion to traverse the tree and find the LCA.
2. If the current node is null, return null.
3. If the current node is one of the target nodes, return the current node.
4. Recursively find the LCA in the left and right subtrees.
5. If both left and right subtrees have a valid LCA, the current node is the LCA.
6. If only one subtree has a valid LCA, return that LCA.

Solution: Here's a Python solution using recursion: `python 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': if not root or root == p or root == q: return root

    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    
    if not left:
        return right
    if not right:
        return left
    
    return root

` This solution has a time complexity of O(n), where n is the number of nodes in the tree, and a space complexity of O(h), where h is the height of the tree.