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
root of a binary tree, return the lowest common ancestor (LCA) of two given nodes,
q. If either node
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
q in a binary tree
T is the lowest node that has both
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.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Explanation: The LCA of nodes 5 and 1 is 3.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Explanation: The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
Explanation: Node 10 does not exist in the tree, so return null.
- The number of nodes in the tree is in the range
-109 <= Node.val <= 109
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.
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:
left = dfs(root.left, p, q)
right = dfs(root.right, p, q)
if root == p:
self.p_found = True
if root == q:
self.q_found = True
if left and right:
return left or right
ans = dfs(root, p, q)
if(self.p_found == False or self.q_found == False):
We need to traverse the entire graph to find the nodes in the graph. Hence the time complexity is O(N).
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).