# Lowest Common Ancestor of a Binary Tree — Day 104(Python)

Today we will be looking at a tree problem. It is a variation of the lowest common ancestor tree problem that we solved sometime back. The link to that problem can be found here. Let us look into today’s problem and how it is different from the previous question.

**1644****. Lowest Common Ancestor of a Binary Tree II**

Given the `root`

of a binary tree, return *the lowest common ancestor (LCA) of two given nodes, *`p`

* and *`q`

. If either node `p`

or `q`

**does not exist** in the tree, return `null`

. All values of the nodes in the tree are **unique**.

According to the **definition of LCA on Wikipedia**: “The lowest common ancestor of two nodes `p`

and `q`

in a binary tree `T`

is the lowest node that has both `p`

and `q`

as **descendants** (where we allow **a node to be a descendant of itself**)". A **descendant** of a node `x`

is a node `y`

that is on the path from node `x`

to some leaf node.

**Example 1:**

**Input:** root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

**Output:** 3

**Explanation:** The LCA of nodes 5 and 1 is 3.

**Example 2:**

**Input:** root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

**Output:** 5

**Explanation:** The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.

**Example 3:**

**Input:** root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10

**Output:** null

**Explanation:** Node 10 does not exist in the tree, so return null.

**Constraints:**

- The number of nodes in the tree is in the range
`[1, 104]`

. `-109 <= Node.val <= 109`

- All
`Node.val`

are**unique**. `p != q`

**Follow up:** Can you find the LCA traversing the tree, without checking nodes existence?

Now, the difference between this question and one that we solved earlier is, In this question, there is a possibility that the nodes may or may not exist. It means it is vital that we traverse through the entire tree.

One way to solve this problem is by having two boolean flags. Whenever we find our required node, we change the value of that boolean flag. This way we can know if we found both the nodes.

We will be using recursion to traverse through the tree.

- Base condition -> We stop traversing tree if the the root is None.
- Until then we keep moving left and right until reaching the leaf node. If the root is equal to any of the required node, we change the value in the boolean flag and return root.
- If both the flags are true, then we return the value of root, else we return None.

`class `**Solution**:

def **lowestCommonAncestor**(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

self.p_found = False

self.q_found = False

def **dfs**(root, p, q):

if root == None:

return root

left = **dfs**(root.left, p, q)

right = **dfs**(root.right, p, q)

if root == p:

self.p_found = True

return root

if root == q:

self.q_found = True

return root

if left and right:

return root

return left or right

ans = **dfs**(root, p, q)

if(self.p_found == False or self.q_found == False):

return None

return ans

**Complexity analysis.**

**Time Complexity**

We need to traverse the entire graph to find the nodes in the graph. Hence the time complexity is O(N).

**Space Complexity**

We are recursively traversing through the graph to find the nodes. We need to traverse the entire graph to find the nodes in the graph, and recursion is internally stored as a stack. Therefore the space complexity is O(N).