Leetcode discuss: 236. Lowest Common Ancestor of a Binary Tree

Here is the article.

May 26, 2020
I like to review my pratice one year ago before I prepared onsite from Amazon and Facebook in August 2010. Here is the link of code written in May 7, 2019 with timeout, missing backtracking and other issues.

There are so many issues in the practice. I like to write reviews one by one. The code is added after the review.

1. Function design has redundancy, traversalPreorder's argument TreeNode current can be removed;
2. Function traversalPreorder can be simplified, find root to p only, and it can be called twice to get root to p and root to q;
3. Need to learn how to optimize space complexity, apply backtracking technique;
4. List prefix has design issue; Ony Add API is called, in other words, the node is added to the list, but there is no place to remove a node;
5. More on step 4, work on a simple tree, root node is 1, left node is 2, right node is 3, preorder traversal, p is right node, then root to p should be [1, 3]; how to work with traversal of [1, 2, 3], root, left, right, and 2 should be removed from the path. Play a few time how to add nodes to the path, in and out, get familiar with tree recursive structure;
6. Three if statement inside traversalPreorder function,

if (current == p && current == q)

should be removed;

Advices

Write a preorder traversal using backtracking, practice is here. The solution is easy to read, preorder traversal and backtracking with optimized space complexity.

The following is the copy of the post with code written in May 7, 2019.

May 3 2019
It is my practice in one of mock interview on this platform. I like to take approach to use preorder traversal to find given two nodes and record the path for each node.

I came cross the time out issue. I like to do some research and get ideas how to fix the issue to work with Leetcode online judge. Any tips? Really appreciated.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lowest_common_ancestor_236_timeout
{
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}

class Program
{
    static void Main(string[] args)
    {
    }

    public static List<TreeNode> rootToP, rootToQ;

    /// <summary>
    /// Leetcode 236 lowest common ancestor in binary tree
    /// - in general case, I like to propose the idea to find both nodes in the tree first, 
    /// and also the path infomration will be recorded. 
    /// 
    /// Problem found: 
    /// Time out in one of test cases
    /// </summary>
    /// <param name="root"></param>
    /// <param name="p"></param>
    /// <param name="q"></param>
    /// <returns></returns>
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if (root == null || p == null || q == null)
            return null;

        rootToP = new List<TreeNode>();
        rootToQ = new List<TreeNode>();

        var newList = new List<TreeNode>();
        traversalPreorder(root, root, p, q, newList);

        if (rootToP.Count == 0 || rootToQ.Count == 0)
        {
            return null;
        }

        int index = 0;
        TreeNode ancestor = null;
        while (index < rootToP.Count && index < rootToQ.Count)
        {
            if (rootToP[index] == rootToQ[index])
            {
                ancestor = rootToP[index];
            }
            else
                break;
            //
            index++;
        }

        return ancestor;
    }

    private void traversalPreorder(TreeNode root, TreeNode current, TreeNode p, TreeNode q, List<TreeNode> prefix)
    {
        prefix.Add(current);

        if (current == p && current == q)
        {
            foreach (var item in prefix)
            {
                rootToP.Add(item);
                rootToQ.Add(item);
            }
        }

        if (current == p)
        {
            foreach (var item in prefix)
            {
                rootToP.Add(item);
            }
        }

        if (current == q)
        {
            foreach (var item in prefix)
            {
                rootToQ.Add(item);
            }
        }

        if (rootToQ.Count > 0 && rootToP.Count > 0)
            return;

        if (current.left != null)
        {
            var newList = new List<TreeNode>(prefix);

            traversalPreorder(root, current.left, p, q, newList);
        }

        if (current.right != null)
        {
            var newList = new List<TreeNode>(prefix);

            traversalPreorder(root, current.right, p, q, newList);
        }
    }
}

}