236: Lowest common ancestor - practice after mock interview

June 15, 2019

Introduction

Life is such great experience. I like to be an interviewer and also I like to master the tree algorithm called lowest common ancestor. But somehow I will have to train myself to focus, catch up whatever the interviewee writes in the interview.

Case study

I wrote a solution based on mock interview on June 14, 2019. Here is the post titled C# find path for two give nodes in two passes case study in 2019.

Here is the post I share.

It was my mock interview on June 14, 2019 10:00 PM. As an interviewer, the interviewee was asked to solve the lowest common ancestor in binary tree. The interviewee wrote a python code and he finished the code in less than 35 minutes. I wrote a C# solution based on his practice.

Here are highlights:

1. Use depth first search to find the node, preorder traversal, all nodes from the node to the root are saved in a hashset;
2. Second search will check the hashset and the first node in the hashset will be lowest common ancestor;
3. DFS function is designed to return bool value, whereas false value for termination of path, true value to continue to build a path.

Here is the blog to contain the mock interview original python code.

Highlights of super performance of interviewee:

1. He asked if there is optimal solution with time complexity O(logN);
2. He proposed naive solution to find the path for node p using DFS;
3. He asked me if I saw the idea before. He explained to me that return false is part of design, make sure lowest common ancestor is found and then stop update on variable answer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public static HashSet<TreeNode> path;
    public static TreeNode answer; 
    
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        path = new HashSet<TreeNode>();
        answer = null;
        
        DFS(root, p);
        DFS(root, q);
        
        return answer; 
    }
    
    /// The second call will try to find the lowest common ancestor
    /// based on the path found by the first call with the given node    
    private static bool DFS(TreeNode current, TreeNode find)
    {
        if(current == null)
            return false;
        
        if(current == find)
        {
            if(path.Contains(current))
            {
                answer = find; 
                return false;
            }
            
            path.Add(find);
            return true;
        }
        
        var left = DFS(current.left, find); 
        if(left == true)
        {
            if(path.Contains(current))
            {
                answer = current;
                return false;
            }
            
            path.Add(current);
            return true; 
        }
        
        var right = DFS(current.right, find); 
        if(right == true)
        {
            if(path.Contains(current))
            {
                answer = current;
                return false;
            }
            
            path.Add(current);
            return true; 
        }
        
        return false; 
    }    
}

Actionable Items

It is hard to push myself to think hard. 

Here are highlights how I make progress on this idea to find path to solve lowest common ancestors. 

1. Find path from root to given node p, path from root to given node q, and then compare two list, find lowest common ancestor. 

2. Actually we do not really need to find the whole path, save  one path on hashset, and then find lowest common ancestor in the second round traversal of tree to find node q. 

3. We do not need to save second path for second search node at all, just one step at a time to compare with first node's path saved in hashset. 

Also, I learn to work on the path from given node to root instead of root to given node.