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.