Smallest Subtree with all the Deepest Nodes

This was an interesting problem that required three very clear steps to solve it in quadratic time. Here is the problem: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.

A node is deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is that node, plus the set of all descendants of that node.

Return the node with the largest depth such that it contains all the deepest nodes in its subtree.

Example 1:

Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:



We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.

Note:

• The number of nodes in the tree will be between 1 and 500.
• The values of each node are unique.

To me the notes (highlighted) give a lot of important information to solving the problem. First, it tells us that it might be OK to go up to N^2. Second, it tells us that we can use a Hash Tablet to map each number to its corresponding node since each node contains a unique number.

So here are the three very well-defined steps to solving this problem (module special cases):

1) Find the deepest path length and map each leaf to its corresponding path.
Finding the deepest path length will return a number and can be done with a simple DFS. But in addition to doing that, as you reach each leaf, store a mapping between that leaf and its path, and you can represent the path as a list of integers. Use a hash table to make the mapping <number> <path as a list>. Complexity will be n-time, n-space.

2) Find all the deepest paths.
Using the information from (1), you can go thru the hash map and collect all the deepest paths. This is done in linear time too.

3) Find the deepest common node.
At last, you have a list of lists for the deepest paths. You need to find the deepest common node. This can be done in time proportional to the length of the list of paths times the length of the path, hence worst case around N^2.

Code is below, cheers, ACC.

public class Solution
{
    public TreeNode SubtreeWithAllDeepest(TreeNode root)
    {
        //Special case
        if (root == null || (root.left == null && root.right == null)) return root;

        //Part 1: find the max path len and also map each leaf node to its path
        Hashtable nodeToPath = new Hashtable();
        Hashtable numberToNode = new Hashtable();
        int maxPathLen = 0;
        FindDeepPaths(root, new List(), ref nodeToPath, ref numberToNode, 0, ref maxPathLen);

        //Part 2: find all the deep paths
        List> deepPaths = new List>();
        foreach (int k in nodeToPath.Keys)
        {
            List path = (List)nodeToPath[k];
            if (path.Count == maxPathLen)
            {
                deepPaths.Add(path);
            }
        }

        //Part 3: find the deepest common node
        if (deepPaths.Count == 1) return (TreeNode)numberToNode[deepPaths[0][deepPaths[0].Count - 1]];

        int resultIndex = -1;
        for (int i = 0; i < maxPathLen; i++)
        {
            int currentNode = deepPaths[0][i];
            bool found = false;
            for (int j = 1; j < deepPaths.Count; j++)
            {
                if (deepPaths[j][i] != currentNode)
                {
                    found = true;
                    break;
                }
            }
            if (found)
            {
                return (TreeNode)numberToNode[deepPaths[0][resultIndex]];
            }
            resultIndex = i;
        }

        return null;
    }

    private void FindDeepPaths(TreeNode node,
                                List path,
                                ref Hashtable nodeToPath,
                                ref Hashtable numberToNode,
                                int pathLen,
                                ref int maxPathLen)
    {
        if (node == null)
        {
            return;
        }

        numberToNode.Add(node.val, node);

        if (node.left == null && node.right == null)
        {
            path.Add(node.val);
            nodeToPath.Add(node.val, new List(path));
            path.RemoveAt(path.Count - 1);
            pathLen++;
            maxPathLen = Math.Max(maxPathLen, pathLen);
            return;
        }

        path.Add(node.val);
        FindDeepPaths(node.left, path, ref nodeToPath, ref numberToNode, pathLen + 1, ref maxPathLen);
        path.RemoveAt(path.Count - 1);

        path.Add(node.val);
        FindDeepPaths(node.right, path, ref nodeToPath, ref numberToNode, pathLen + 1, ref maxPathLen);
        path.RemoveAt(path.Count - 1);
    }
}