You need to increase the stack size as well. on top of your code add these 2 lines

import threading

threading.stack_size(2**26)

And call your main function in the end of your code by using the line,

threading.Thread(target=main).start()

If you still get RE, increase the stack size to 2**27 or 2**28, or if you get TLE then decrease it to 2**25 or 2**24 Hope this helps

Firstly your BFS solution is definitely not a BFS, it is still a DFS, just written using your own stack. To get BFS you need to use collections.deque with append and popleft...

About recursion in Python, it sucks

Here is the thing, deep recursion in Python just doesn't work. To my understanding Python uses pretty large stack frames, so the stack is going to get filled up very quickly, also Python doesn't do any kind of tail call optimization. So you just simply can't do deep recursion in Python.

The recursion limit is just Pythons way of dying nicely (giving a catchable exception) instead of crashing. So increasing the limit is pretty much just going to make your code go from dying from an exception to crashing. The default limit is set to a 1000 for a reason.

So what if you still want to do deep recursion in Python? The only thing I found feasible is to manually do it with your own stack. Like what you did in your second solution. It's not pretty but that is the only thing I've found to work and be reasonably fast. One nice thing is that this means that you can switch between BFS and DFS without having to change much of the code.