BFS one pass beats 100% with clear explanation
All node have highest depth should all located on the last row of the input tree.\n2. If there is only one node on last row. We just need to return that node.\n
1. All node have highest depth should all located on the last row of the input tree.\n2. If there is only one node on last row. We just need to return that node.\n3. If there are multiple nodes on the last row the we have to find the lowest common ancestor of the most left node and most right node.\n4. We can achieve this by doing one level-order-traversal to find the last row of the input tree and meanwhile use a hashmap to store the parent-child relationship of all node.\n\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int x) { val = x; }\n * }\n */\n public class Solution {\n\n public TreeNode SubtreeWithAllDeepest(TreeNode root)\n  {\n      if (root == null) return root;\n\t  Dictionary<TreeNode, TreeNode> dict = new Dictionary<TreeNode, TreeNode>();\n      var q = new Queue<TreeNode>();\n      var lastrow = new List<TreeNode>(); \n\t  \n\t  //Find the last row of input tree same as level order traversal\n      q.Enqueue(root);\n\n      while(q.Count != 0)\n      {\n        lastrow = new List<TreeNode>();\n        var level = q.Count;\n        for(int i = 0; i< level;i++)\n        {\n          var temp = q.Dequeue();\n          if(temp.left != null) {\n            q.Enqueue(temp.left);\n            dict.Add(temp.left, temp);\n          }\n          if(temp.right != null) {\n            q.Enqueue(temp.right);\n            dict.Add(temp.right, temp);\n          }\n          lastrow.Add(temp);\n        }\n\n     }   \n         \n    if(lastrow.Count == 1) return lastrow.First();\n\t// find the lowest common ancestor of most left and most right node on last row\n    var left = lastrow.First();\n    var right = lastrow.Last();\n\n    while(dict[left] != dict[right])\n    {\n      left = dict[left];\n      right = dict[right];\n    }\n\n    return dict[left];\n  }\n}\n```
['Breadth-First Search']