Example: 1 / \ 2 3 / \ / \ 4 5 6 7 ==> LCA of 6 and 4 is 1, LCA of 4 and 5 is 2.
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