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

Photo by Adarsh Kummur on Unsplash

We will be looking at a Tree Problem today. Before jumping into the problem, let us understand a few features of the binary tree.

A binary tree is a data structure where each node can have at the most two children. The topmost part of a tree is called the root node, and the ends are called the leaf. A tree of any form cannot have a cycle in it. An example of a binary tree is as follows.

Example of a binary tree.

236. Lowest Common Ancestor of a Binary Tree

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).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

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, since a node can be a descendant of itself according to the LCA definition.

Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the binary tree.

Solution:

1. Maintain a dictionary that provides information about the child node and their parent node.

a. Use a stack that holds nodes to be visited.

b. Use a dictionary that holds information about the child node and their parent node. Initialize it with key as root and value as none, which implies the root does not have any parent node.

c. Run the loop until elements are present in the stack.

i. Pop node from the stack.

ii. Check if the node has any left child. If yes, push the left child of the node to stack, and in the dictionary mention key as left child and value as the current node. Perform the same operation if we have the right child for the current node.

d. Once the tree is traversed completely, create a set that will hold ancestors from node1 to the root node.

e. Traverse from node2 to root node, and check if any of the nodes are present in the above set. If we find a common node, return the node value.

The algorithm will look as below.

class LowestCommonAncestorFinder:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        stack = [root]
        parent = {root: None}
        while stack:
            node = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)
        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]
        while q not in ancestors:
            q = parent[q]
        return q

Complexity analysis.

Time Complexity

We are traversing through the complete graph to mark the parent-child relationship. Therefore time complexity O(N), where N is the number of nodes.

Space Complexity

We are creating a dictionary to mark the parent-child relationship in the tree. Therefore the space complexity is O(N), where N is the number of nodes.

We can solve the above problem using recursion.

1. Before beginning to solve the problem using recursion, we need to understand the base conditions. When we reach the end of the tree or we meet either of the nodes, then the base condition is met.
2. Till reaching the base condition, move left and right to the current node, and storing the values in the left and right variables respectively.
3. Verify if left and right are present. If yes, return the root value i.e parent.
4. Else Return whichever is not empty among left and right variables.

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

        if  root == None or root == p or root == q :
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        print(root.val,left, right)
        return left if left  else right

Complexity analysis.

Time Complexity

In the worst-case scenario, we might 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. In the worst-case scenario, we might need to traverse the entire graph to find the nodes, and recursion is internally stored as a stack. Therefore the space complexity is O(N).