public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        Map<TreeNode, TreeNode> map = bfs(root);
        LinkedList<TreeNode> pPath = new LinkedList<>();
        TreeNode pp = p;
        while (pp != null) {
            pPath.addFirst(pp);
            pp = map.get(pp);
        }
        LinkedList<TreeNode> qPath = new LinkedList<>();
        TreeNode qq = q;
        while (qq != null) {
            qPath.addFirst(qq);
            qq = map.get(qq);
        }
        ListIterator<TreeNode> pit = pPath.listIterator();
        ListIterator<TreeNode> qit = qPath.listIterator();
        while (pit.hasNext() || qit.hasNext()) {
            if (!pit.hasNext()) return pit.previous();
            if (!qit.hasNext()) return qit.previous();
            TreeNode pcurrent = pit.next();
            TreeNode qcurrent = qit.next();

            if (pcurrent != qcurrent) return map.get(pcurrent);
        }
        return root;
    }
We first find path from root to p and from root to q nodes.
Then we traverse both paths till the values in arrays are same.
Return the common element just before the mismatch.
src/problems/medium/LowestCommonAncestorofaBinaryTree.java