BFS + LCA
What is depth of a node?\n> \n> The distance from the root to a node\n \n>How do we tell if a node is deepest?\n>\n>By BFS level order traversal. Nodes in the l
> What is depth of a node?\n> \n> The distance from the root to a node\n \n>How do we tell if a node is deepest?\n>\n>By BFS level order traversal. Nodes in the last level should be deepest (if root is at level 0).\n\n> The problem is actually asking the LCA among deepest nodes\n> \n> For deepest nodes `[ leftmost , ..., rightmost ]` (nodes are in order), `lca(leftmost , ..., rightmost) = lca(leftmost, rightmost)`\n>\n> So during BFS level order traversal, we only have to keep track of the leftmost and rightmost node.\n****\n```\n    public TreeNode subtreeWithAllDeepest(TreeNode root) {\n        if (root == null) {\n            return null;\n        }\n        // Get list of deepest nodes\n        List<TreeNode> deepestNodes = getDeepestNodes(root);\n        \n        TreeNode lca = deepestNodes.get(0);\n        for (int i = 1; i < deepestNodes.size(); i++) {\n            lca = getLowestCommonAncestor(root, lca, deepestNodes.get(i));\n        }\n            \n        return lca;\n    }\n    \n    private List<TreeNode> getDeepestNodes(TreeNode root) {\n        List<TreeNode> levelNodes = new ArrayList<>();\n        \n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n        \n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            levelNodes = new ArrayList<>();\n            for (int i = 0; i < size; i++) {\n                TreeNode node = queue.poll();\n                levelNodes.add(node);\n                \n                if (node.left != null) {\n                    queue.offer(node.left);\n                } \n                if (node.right != null) {\n                    queue.offer(node.right);\n                }\n            }\n        }\n        \n        return levelNodes;\n    }\n    \n    private TreeNode getLowestCommonAncestor(TreeNode root, TreeNode left, TreeNode right) {\n        if (root == null) {\n            return null;\n        }\n        if (root == left || root == right) {\n            return root;\n        }\n        TreeNode leftAns = getLowestCommonAncestor(root.left, left, right);\n        TreeNode rightAns = getLowestCommonAncestor(root.right, left, right);\n        if (leftAns != null && rightAns != null) {\n            return root;\n        } else if (leftAns == null) {\n            return rightAns;\n        } else { // if (rightAns == null) {\n            return leftAns;\n        } \n    }\n```
[]