Find lowest common ancestor in tree

You are given the root of a binary search tree (BST) and two distinct nodes p and q that are guaranteed to exist in the tree.

Task (BST case):

• Find the lowest common ancestor (LCA) of nodes p and q.
• The LCA is defined as the lowest (deepest) node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Assumptions:

• The tree satisfies the BST property: for any node x, all nodes in the left subtree have values < x.val, and all nodes in the right subtree have values > x.val.
• You may receive p and q as node references or as values; clarify with the interviewer, and handle one consistent version.

Follow-up:

• How would your approach change if the tree is a general binary tree without the BST property?
• In the general binary tree case:
  • The tree may not be balanced.
  • Node values are not ordered.
  • p and q are still guaranteed to exist.

Describe algorithms for both the BST and the general binary tree cases and analyze their time and space complexity.

Lowest Common Ancestor in a BST

Given BST level-order values and two node values, return their LCA value.

Examples

Example 1

Input: ([6,2,8,0,4,7,9,None,None,3,5], 2, 8)
Output: 6

Explanation: Root split.

Example 2

Input: ([6,2,8,0,4,7,9,None,None,3,5], 3, 5)
Output: 4

Explanation: LCA in left subtree.

Hints

1. Use deterministic tie-breaking for prompts with multiple valid outputs.
2. For design-style APIs, simulate operations with explicit inputs.

Lowest Common Ancestor in a General Binary Tree

Given general level-order tree values and two node values, return their LCA value.

Examples

Example 1

Input: ([3,5,1,6,2,0,8,None,None,7,4], 5, 1)
Output: 3

Explanation: Root LCA.

Example 2

Input: ([3,5,1,6,2,0,8,None,None,7,4], 7, 4)
Output: 2

Explanation: Nested LCA.

Hints

1. Use deterministic tie-breaking for prompts with multiple valid outputs.
2. For design-style APIs, simulate operations with explicit inputs.