public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
    if (root == null || p == null || q == null) return root;
    // create parents
    Dictionary<TreeNode, TreeNode> parentHash = new Dictionary<TreeNode, TreeNode>();
    parentHash.Add(root, null);
    DFS(root, parentHash);
    // find path of p
    Dictionary<TreeNode, bool> pNodePathHash = new Dictionary<TreeNode, bool>();
    TreeNode node1 = p;

    while (node1 != null)
    {
        pNodePathHash.Add(node1, true);
        node1 = parentHash[node1];
    }
            
    // walk from q to root
    node1 = q;

    while (node1 != null)
    {
        //qNodePathList.Add(node1);
        if (pNodePathHash.ContainsKey(node1))
        {
            return node1;
        }
        node1 = parentHash[node1];
    }

    return null;
}

public void DFS(TreeNode node, Dictionary<TreeNode, TreeNode> parentHash)
{
    if (node.left != null)
    {
        parentHash.Add(node.left, node);
        DFS(node.left, parentHash);
    }

    if (node.right != null)
    {
        parentHash.Add(node.right, node);
        DFS(node.right, parentHash);
    }
}