DIY: Lowest Common Ancestor of a Binary Tree

Problem statement

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

Input

The first argument will be the root node of a binary tree. The second and third arguments will be two other nodes in the binary tree. The following is an example input:

    3
   / \
  9  20
    /  \
   15   7

input = [3, 15, 7]

Output

The output would be the value of the LCA node. For the above input, the output will be:

20

The node with the value 20 is the LCA of the nodes with the values 15 and 7.

Coding exercise

For this coding exercise, you need to implement the function LCA(root, node1, node2), where root is the root node of the binary tree. You need to find the LCA of node1 and node2. The function should return the value of the LCA node.