236. Lowest Common Ancestor of a Binary Tree | LeetCode Medium | Python Solution | Binary Tree | DFS

Leetcode medium problem 236. Lowest Common Ancestor of a Binary Tree, detailed explanation and solution in python language.

#leetcode #python #solution

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given the root of a tree, and also two random nodes of that tree.
we need to find out the lowest common ancestor of these two random nodes.

for example, here if p=5 and q=1 are the two given nodes, then the node 3 is the lowest ancestor common to both the nodes 5 and 1.
an important thing to note here is that a node can be an ancestor of itself.
so, if p=5 and q=7 are the two given nodes, then the node 5 is the lowest ancestor common to both the nodes 5 and 7.

to find out the lowest common ancestor, what we can do is, run a DFS, ie, Depth first search inorder traversal on the given tree.
inorder traversal means, we will be first looking at the left node, then the current node and at last the right node.
for example, inorder traversal of this tree will be 6, 5, 2.

and if there are subtrees, we need to do inorder traversal on subtrees as well.
for example, inorder traversal of this tree will be 6, 7, 4, 2, 5.

we are required to find two nodes p and q.
so lets look at different scenarios of occurances of these two nodes.

the first scenario is, we found one node on the left subtree, and the other node on the right subtree.
in this case, we have found a total of two nodes at the current node.
and therefore, the current node will be the lowest common ancestor of those two nodes.

the second scenario is, we found one node on the current node itself, and the other node on the left subtree.
in this case, we have found a total of two nodes at the current node.
and therefore, the current node will be the lowest common ancestor of the two nodes.

the third scenario is, we found one node on the current node itself, and the other node on the right subtree.
in this case also, we have found a total of two nodes at the current node.
and therefore, the current node will be the lowest common ancestor of the two nodes.

in all the three scenarios, the nearest node at which we are getting a total of 2 found out nodes is the lowest common ancestor.

with this observation, lets take an example and solve the problem.
in this example, p is 5 and q is 1.
lets do an inorder traversal on this tree.
at node 5, we have found 1 required node.

now lets continue the traversal.
we found 0 required nodes at 6, 7, 4 and 2.
so lets return the results to the respective parent nodes.
from node 5, we will return 1 to its parent node 3.

on continuing the traversal, we have found 1 more required node.
lets continue the traversal to its subtrees.
since there are no required nodes found, we will return 0 to its parent node.
from node 1, we will return 1 to its parent node 3.
so at node 3, we have a total of 2 required nodes found. and hence it is the lowest common ancestor.

now, lets take another example.
in this example, p is 5 and q is 4.
on performing an inorder traversal, we have found 2 required nodes at node 5. and hence it is the lowest common ancestor.

lets have a variable initially set to None for storing the result.
and at last we will be returning it.

we will write a seperate function for traversing through each nodes recursively.
we will start the function call with the root node of the tree.

since we are doing an inorder traversal, we will recursively traverse through the left and right nodes in the beginning.
in this function, we need to check whether the current node is one of the node we are looking for. if yes, then we will set this variable to 1 else 0.

we will then check whether the total number of nodes found out at this current node is equal to 2.
If yes, that means we have found out the lowest common ancestor.
and hence we will be storing the result in this variable.

so at last, if we have found any node from the left, right or the current node, we will be returning 1 to the current node parent. if nothing found, then we will be returning 0 to the current nodes parent node.