Leetcode series: DFS and BFS in Tree (Part 2)

A photo by Nik Shuliahin on Unsplash.

Hi folks! Today back to the Leetcode series, I will write about problem 236, which is the next problem in the topic DFS and BFS in Tree. I encourage you should do this problem by yourself first then back to this blog, and we can discuss the problem more interesting.

“A leetcode a day, keeps unemployment away”

Disclaimer: I do not encourage you should do a lot of Leetcode without a plan. English is not my mother language, and I want to write blogs to improve my writing and English skill as well as I want to save and share what I’ve learned in computer science or anything else every day with everyone. I really want to improve myself in anything about computer science and my English so feel free to correct me on any things that I wrote in the blog, and my English as well. I really appreciate that.

Note: I’ve followed to do Leetcode problems based on data structure patterns at this site. I think it will be more efficient and easy to understand as well as “remember” the knowledge or the pattern of a data structure than doing a lot of random problems on Leetcode without any plan.

Now let’s go to the problem.

Problem 236:

Example 1:

An example of the problem on Leetcode.

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:

An example of the problem on Leetcode.

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.

Requirement:

We have to find the lowest common ancestor of 2 given nodes p and q, and you can read more about what is LCA here. Basically, the LCA is the “nearest” node that has node p and node q as descendants. Especially, a node can be a descendant of itself.

First thought:

Firstly, I think we just need to traverse through the tree, and find the node value of each node whether is equal to the p or q then return that node. So we just need to recursively call the function to find them in the left node of the root and the right node of the root.

Logical thinking:

Now, my logic to solve this problem is that wewill go to every node and check its value to see whether it is equal to the p or q node, if it is a null value, just return null. Then, create 2 variables left and right to recursively find in the left subtree and the right subtree.

So, why I said this is a DFS approach? Because it will be recursively called in the left tree until it goes to the deepest of the tree, then it will go to the right node of those nodes. It is a basic idea of the DFS (Depth-First-Search), it will go by the depth of the tree, and in this case, we go to the left part first.

So, basically now we just need to check the left variable or right variable that we created to traverse the tree if both variables are not null, it means that our root is the lowest common ancestor then we will return the root, else if the left is null then our result must be the right and vice versa. Sounds good?

Now, let’s improve our algorithm a little bit, we will create 2 boolean variables to check whether we found the q node or p node, so when we found those 2 nodes in the left subtree we do not need to check in the right subtree anymore, just return the left.

Here is my implementation:

class Solution {
        boolean foundP= false, foundQ= false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         if(root == null) return null;
        if(root.val == q.val){
            foundQ = true;
            return root;
        }
        if(root.val == p.val){
            foundP= true;
            return root;
        }
       TreeNode left = lowestCommonAncestor(root.left,p,q);
        // if we found p and q at left subtree, just return it !! 
        if(foundQ && foundP){
            return left;
        }
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //if we have not found p and q at left subtree, it must be in right or root.
        
       if(left != null && right != null){ 
           // if left and right is not null, it must be the root
           return root;
       }
        return left == null ? right : left;
        
    }
}

Feel free to correct me on anything, and improve my solution as well.

Thank you, guys! And happy coding!