case study: lowest common ancestor in binary tree algorithm

I like to write a short case study how good the interviewee is as a senior engineer in Microsoft with more than 7 years experience.

Case study

Here is the gist.

The interviewer wrote a working solution first, and I challenged him to solve edge case if p or q is not in binary tree, and then he added a function to check p is not binary tree and do some checking before LCA is found.

	import java.io.*;
	import java.util.*;
	/*
	* To execute Java, please define "static void main" on a class
	* named Solution.
	*
	* If you need more classes, simply define them inline.
	*/
	class Solution {
	public static void main(String[] args) {
	ArrayList<String> strings = new ArrayList<String>();
	strings.add("Hello, World!");
	strings.add("Welcome to CoderPad.");
	strings.add("This pad is running Java " + Runtime.version().feature());
	for (String string : strings) {
	System.out.println(string);
	}
	}
	class TreeNode
	{
	public int val;
	public TreeNode left, right;
	}
	// p - 7, q = 8, q is not in the tree -
	TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q)
	{
	if(!checkNodes(root,p) && !checkNodes(root,q){
	return null;
	}
	return findLCAValid(root,p,q);
	}
	TreeNode findLCAValid(TreeNode root, TreeNode p , TreeNode q){
	if (root == null) return null;
	if (root == p || root == q ) return root;
	TreeNode leftnode = findLCAValid(root.left, p, q);
	TreeNode rightnode = findLCAValid(root.right, p ,q);
	if (leftnode != null && rightnode != null){
	return root;
	}
	if (leftnode == null) return rightnode;
	return leftnode;
	}
	boolean checkNodes(TreeNode root, TreeNode p){
	if (root == null) return false;
	if (root == p) return true;
	return checkNodes(root.left,p) || checkNodes(root.right,p);
	}
	}
	/*
	Your previous Plain Text content is preserved below:
	given a binary tree, a root node, node p and node q, find lowest common ancestor.
	1
	/ \
	3 5
	/ \
	7 9
	\
	15
	above example, p = 7, q = 15, then LCA = node 3
	p = 7, q = 3, then LCA = node 3
	p = 7, q = 5, then LCA = node 1
	p = 7, q = 8 not in tree, then LCA = null
	class TreeNode
	{
	public int val;
	public TreeNode left, right;
	}
	TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q)
	{
	if (root == null)
	}
	*/

view raw FindlowestCommonAncestor.java hosted with ❤ by GitHub

After that, I asked him to think about second idea to solve the problem; he wrote the idea using stack, after 10 minutes, I stepped in to ask him to find path from root to p and root to q first, using an example, two lists and then find LCA.

He wrote the algorithm.

Here is the gist.

I reviewed the code using binary tree with test case: Root node with value 1, left child with value 2, right child with value 3, p = node with value 3, find Root to p, [1, 3]. And his code works perfectly.

	import java.io.*;
	import java.util.*;
	/*
	* To execute Java, please define "static void main" on a class
	* named Solution.
	*
	* If you need more classes, simply define them inline.
	*/
	class Solution {
	public static void main(String[] args) {
	ArrayList<String> strings = new ArrayList<String>();
	strings.add("Hello, World!");
	strings.add("Welcome to CoderPad.");
	strings.add("This pad is running Java " + Runtime.version().feature());
	for (String string : strings) {
	System.out.println(string);
	}
	}
	class TreeNode
	{
	public int val;
	public TreeNode left, right;
	}
	///
	// can you write a solution to find path from root to p, and root and q, and then compare two path, find LCA
	p = 7, [1, 3, 7]
	q = 15 [1, 3, 9,15]
	TreeNode findLcaStack(TreeNode root, TreeNode p, TreeNode q){
	if (root == null) return null;
	Stack<TreeNode> stack = new Stack<>();
	//stack.push(root);
	while (root != null || !stack.isEmpty()){
	while (root != null){
	stack.push(root);
	root = root.left;
	}
	TreeNode r = stack.pop();
	root = r.right;
	}
	}
	List<TreeNode> findPath(TreeNode root, TreeNode p){
	List<TreeNode> res = new ArrayList<>();
	dfs(root,res,p);
	return res;
	}
	boolean b = false;
	1
	/ \
	2 3
	p = 3, find path from root to p, [1, 3]
	preorder, [1, 2, 3]
	[1]
	[1,2] <- push 2 and then remove 2 from path
	[1,3] <- 3 p
	void dfs(TreeNode root, List<Integer> res , TreeNode p){
	if (root == null) return;
	/*if (root.left == null && root.right == null){
	}*/
	if (root== p){
	res.add(root);
	b = true;
	return;
	}
	if (b == false){
	res.add(root);
	}
	else{
	return;
	}
	if (b == false){
	dfs(root.left,res,p); // not found
	dfs(root.right,res,p); // found
	if (b == false){
	res.remove(res.size()-1); // 2 <- remove from path
	}
	}
	}
	}
	/*
	Your previous Plain Text content is preserved below:
	given a binary tree, a root node, node p and node q, find lowest common ancestor.
	1
	/ \
	3 5
	/ \
	7 9
	\
	15
	above example, p = 7, q = 15, then LCA = node 3
	p = 7, q = 3, then LCA = node 3
	p = 7, q = 5, then LCA = node 1
	p = 7, q = 8 not in tree, then LCA = null
	class TreeNode
	{
	public int val;
	public TreeNode left, right;
	}
	TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q)
	{
	if (root == null)
	}
	*/

view raw FindLowestCommonAncestor.java hosted with ❤ by GitHub

My feedback as an interviewer 

I shared my showcase with the link, and also the performance of ex-Facebook engineer. Here is the link.