Given the root node of a binary tree with $n$ nodes, your task is to find the lowest common ancestor of two of its nodes, p and q.

Note: The lowest common ancestor of two nodes, p and q, is defined as the lowest node in the binary tree that has both p and q as descendants.

A node can also be a descendant of itself. For example, if q is a descendant of p, and we know that p is a descendant of itself, then p will be the lowest common ancestor of p and q.

Constraints:

• $2 \leq n \leq 500$
• All Node.data are unique.
• p $!=$ q
• p and q exist in the tree.

Start from the root and recursively search the left and right subtrees. At each node, check if it matches either of the two given nodes. If it does, return that node since it’s a potential ancestor. Otherwise, continue searching for the nodes in both subtrees. As the recursion explores the left and right subtrees, it returns a node if one of the given nodes is found or returns null if neither node is found in that subtree.

At each node, if only one of the subtrees returns a non-null result, it means both nodes are located in that subtree. The non-null result propagates upwards as you search for the lowest common ancestor.

If both ...