LCA in Binary Tree

Today I will be writing about the LCA(Least Common Ancestor) for a binary tree.

LCA refers to the node in the binary tree, which is the common ancestor and is closest to the two given nodes or farthest from the root node, yes LCA is defined for two other existing nodes in a binary tree.

Let us quickly jump into the algorithm.

In this algorithm, we check the node we are at, if it is equal to any of the node value for which we are finding the LCA, we simply return it.

Otherwise we check the left and right halves recursively, and if we get both as non null, that means this node is the LCA of the two nodes . Else return the non null part either it can be the left or the right. In this algorithm it is assumed that both the nodes are already present in the tree. For better understanding draw the recursive stacks and dry run the sample tree given in my code.

Please take a look at my code -

I keep sharing such content on DSA and Android Developement regularly, do follow me for more such content. Happy Coding.