Python 3: recursive inorder traversal with early stopping
Idea:\nDo a normal recursive inorder traversal. Add an extra check: if the length of our resulting list res becomes k, then we have enough elements. Break your 
**Idea**:\nDo a normal recursive inorder traversal. Add an extra check: if the length of our resulting list ```res``` becomes ```k```, then we have enough elements. Break your recursion and return the last element in ```res```.\nIt works because an inorder traversal of a BST creates a sorted list.\nProbably ```O(h)``` and ```O(k)``` time and space complexities respectively.\n\n```\ndef kthSmallest_dfs_early_stopping(self, root, k):\n\tres = []\n\tdef _inorder(node):\n\t\tif not node: return\n\t\t_inorder(node.left)\n\t\tif len(res) == k:\n\t\t\treturn\n\t\tres.append(node.val)\n\t\t_inorder(node.right)\n\t_inorder(root)\n\treturn res[-1]\n```\n\n
['Depth-First Search', 'Recursion', 'Python', 'Python3']