Using two complete binary trees of height d as a starting point, some people have proposed joining them together by alternating permutations between their leaves. Such a graph can be presented via a local view in the form of an oracle returning, for a given vertex, the list of its neighbours. The first problem is, given the identifier of one root of the tree, to find the identifier of the other root. In 2003, Childs, Cleve, Deotto, Farhi, Gutmann and Spielman obtained both an exponential lower bound on the number of calls to the oracle for any classical algorithm and a quantum algorithm with a polynomial number of calls. In 2021, Aaronson conjectured that a quantum advantage might exist for the second problem of finding a path between the two roots knowing only one of them. I will discuss some very recent results on this subject and also our work with Shrinidhi Teganahally Sridhara as an extension of my co-supervision of his M1 internship via ReLaX this summer. We propose classical walk analyses for this second problem as well as a quantum algorithm still with an exponential number of calls to the oracle but reaching the best classical lower bound that we know of.