Distance in a Binary Tree - yet another space/time tradeoff

Problem is here: Find Distance in a Binary Tree - LeetCode

1740. Find Distance in a Binary Tree

Medium

Given the root of a binary tree and two integers p and q, return the distance between the nodes of value p and value q in the tree.

The distance between two nodes is the number of edges on the path from one to the other.

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0
Output: 3
Explanation: There are 3 edges between 5 and 0: 5-3-1-0.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7
Output: 2
Explanation: There are 2 edges between 5 and 7: 5-2-7.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5
Output: 0
Explanation: The distance between a node and itself is 0.

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 109
• All Node.val are unique.
• p and q are values in the tree.

With number of nodes = 10^4, you can't go for N^2, and need to be careful with NLogN (may lead to TLE). To achieve O(N)-time, we'll have to use some extra space. Here is one approach:

1. Have a function that finds the path from root to the node (notice that the elements in the tree are unique, which helps)

2. For #1, put the path on a list of integers. This is the extra space, this will be O(N)-space

3. Call FindPath for p and q

4. So far, O(N)-time with O(N)-space

5. Now do a linear parse from 0..Min(FindPath(q), FindPath(p)) looking for the very first mismatch

6. Do some back of the envelope calculation with the index in #5 to find the answer

You can see in the results that the code runs fast at the space expense. As I say, this is fine, space is cheap. My first attempt yielded TLE because I was using string to keep track of the path instead of a proper list. Code is below, cheers, ACC.

public class Solution
{
    public int FindDistance(TreeNode root, int p, int q)
    {
        List lp = new List();
        List lq = new List();

        FindPath(root, p, new List(), ref lp);
        FindPath(root, q, new List(), ref lq);

        int min = Math.Min(lp.Count, lq.Count);
        int index = 0;
        while (index < min)
        {
            if (lp[index] != lq[index]) break;
            index++;
        }

        return lp.Count + lq.Count - 2 * index;
    }

    private bool FindPath(TreeNode current,
                          int target,
                          List currentPath,
                          ref List finalPath)
    {
        if (current == null) return false;

        currentPath.Add(current.val);
        if (current.val == target)
        {
            foreach (int v in currentPath) finalPath.Add(v);
            return true;
        }

        if (current.left != null)
        {
            if (FindPath(current.left, target, currentPath, ref finalPath)) return true;
        }
        if (current.right != null)
        {
            if (FindPath(current.right, target, currentPath, ref finalPath)) return true;
        }

        currentPath.Remove(current.val);
        return false;
    }
}