lowest common ancestor bst

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * map.contains
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //map to hold parent-child relationships and be able to backtrack
        Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
        //stack for traversing the tree, pushing children and popping in a while loop
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

        //put the initial values
        map.put(root, null);
        stack.push(root);

        //fill out the map with all nodes until it has both p and q
        while (!map.containsKey(p) || !map.containsKey(q)){
            if (!stack.isEmpty()){
                TreeNode node = stack.pop();
                if (node.left != null){
                    map.put(node.left, node);
                    stack.push(node.left);
                }
                if (node.right != null){
                    map.put(node.right, node);
                    stack.push(node.right);
                }
            }
        }

        //map now has all nodes up to p and q, now lets filter them out
        //set to hold unique parents of P as we backtrack on the map
        Set<TreeNode> pParents = new HashSet<TreeNode>();
        //node to hold p's highest parent (null, since the root's parent is null)
        TreeNode pParent = map.get(p);
        pParents.add(p);
        while (pParent != null){
            pParents.add(pParent);
            pParent = map.get(pParent);
        }

        //now that we have all of p's parents in a set, lets return the first parent of q
        //that appears in that set (thus, getting the lowest common ancestor)
        TreeNode qParent = map.get(q);
        while(!pParents.contains(qParent)){
            qParent = map.get(q);
        }

        //since the while loop stopped, qParent is suddenly in the ancestors set of p
        //so its the first occurance of a shared parent
        return qParent;

    }
}