Given the root node of a binary tree, write a program to find the lowest common ancestor (LCA) of two given nodes in the tree.

Problem Note

• Lowest Common ancestor: The lowest common ancestor is defined between two nodes node1 and node2 as the lowest node in a tree that has both node1 and node2 as descendants (where we allow a node to be a descendant of itself).
• All of the node's values will be unique.
• node1 and node2 are different and both values will exist in the binary tree.
• You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.

Given the following binary tree: root = [5, 6, 3, 1, 7, 9, 4, null, null, 2, 0]

Example 1

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

Example 2

Input: root = [5, 6, 3, 1, 7, 9, 4, null, null, 2, 0]
node1 = 6, node2 = 0
Output: 6
Explanation: The LCA of nodes 6 and 0 is 6, since a node can be a descendant of itself according to the LCA definition.