Java BFS
Use BFS to traverse the tree and get the last level. Then iterate through the last level\'s parents until you get the shared parent node.\n\n\nclass Solution {\
Use BFS to traverse the tree and get the last level. Then iterate through the last level\'s parents until you get the shared parent node.\n\n```\nclass Solution {\n    public TreeNode subtreeWithAllDeepest(TreeNode root) {\n        Queue<TreeNode> q = new LinkedList<TreeNode>();\n\t\tif (root == null)\n\t\t\treturn root;\n       \n        q.add(root);\n        HashMap<TreeNode, TreeNode> mapOfNodes = new HashMap<>();\n        \n        while (!q.isEmpty()) {\n            Queue<TreeNode> tempQ = new LinkedList<TreeNode>();\n            for(TreeNode t: q) {                \n                if(t.left != null) {\n                    tempQ.add(t.left);\n                    mapOfNodes.put(t.left, t);\n                }\n\n                if(t.right != null) {\n                    tempQ.add(t.right);\n                    mapOfNodes.put(t.right, t);\n                }\n            }\n            if(tempQ.size() == 0) {\n                break;\n            }\n            else {\n                q = tempQ;\n            }\n        }\n        \n        return getSharedParent(q, mapOfNodes);\n    }\n    \n    private TreeNode getSharedParent(Queue<TreeNode> q,  HashMap<TreeNode, TreeNode> mapOfNodes) {\n         while(!q.isEmpty()) {\n            if(q.size() == 1) return q.poll();\n            \n            Queue<TreeNode> tempQ = new LinkedList<TreeNode>();\n            for(TreeNode t: q) {\n                if(!tempQ.contains(mapOfNodes.get(t))) {\n                    tempQ.add(mapOfNodes.get(t));\n                }\n            }\n            q = tempQ;\n        }\n        return null;\n    }\n}\n```
['Breadth-First Search', 'Java']