So at each step there are four possibilities to explore, which suggests that with s steps the entire tree has 4^s possibilities with an average of 4^s / 2 before you find the desired one (if it is unique and you have no other information). One question that comes to mind: how many steps are there for a given number, and how does this grow with the size of the number?
