Given a binary tree and two tree nodes, write a method to find LCA (Lowest Common Ancestor) of the two nodes.

Example: 1 / \ 2 3 / \ / \ 4 5 6 7 ==> LCA of 6 and 4 is 1, LCA of 4 and 5 is 2.

Need a **hand?** Try out these hints, one at a time.

The lowest common ancestor node

`N`

of two nodes `n1`

and `n2`

is defined as the lowest node in the tree `T`

that has both `n1`

and `n2`

as descendants and the paths from `N->n1`

and `N->n2`

are the shortest possible.
1. Declare two variables to keep track of the `left`

and `right`

accessors at each level. Let's call them `tempLeft`

and `tempRight`

.

2. As part of the `base`

condition, if `root`

is `null`

, return `root`

.

3. If `root`

is **equal** to `node a`

or `node b`

, return `root`

.

4. Make a recursive call with the left node of the root as the input and assign it to `leftTemp`

. Similarly, assign the output of the recursive call with the `right`

node to `tempRight`

.

5. If either `leftTemp`

or `rightTemp`

are `null`

, return `null`

. Else, return the node that is not null.

public TreeNode findLCA(TreeNode root, TreeNode a, TreeNode b) { }

**C**

**Java**

**Python**