사실 노드를 집어넣을 때마다 모든 이진트리를 탐색하면서 삽입할 노드를 찾는다는 아이디어가 상당히 비효율적으로 보이긴 합니다만... 다른 방법으로 풀렸다고는 하셨고 N이 최대 26으로 매우 작기도 하니 이건 넘어가겠습니다.

find 함수가 재귀적으로 호출될 때, 재귀의 끝에서 어떤 값이 반환되더라도 그 값은 재귀의 시작부분으로 바로 반환되는 게 아닙니다. 대신 해당 반환점 바로 직전의 함수 호출로 반환됩니다.

예를 들어 현재 찾고자 하는 노드가 루트에 있지 않고, 루트에 자식이 있는 상황에서 프로그램의 흐름을 따라가보겠습니다. 20행에서 find 함수를 호출하여 27행으로 넘어가는데, 첫 if문의 조건은 거짓이므로 그냥 넘어갑니다. 이후 두 가지 if문을 하나씩 둘러보면서 find함수를 호출합니다.

하지만 31~34행을 하나씩 넘어가보면 반환되는 것이 아무것도 없습니다. 보시다시피 return 키워드가 하나도 없기 때문에, 첫 find 함수에서 반환되는 게 없습니다. 따라서 None이 반환됩니다.

재귀함수 호출시 반환되는 값은 재귀함수의 끝에서의 반환값이 아닙니다. 결국 호출한 그 첫 함수가 반환하는 값이 반환되므로, 이를 고려해서 함수를 고치면 해결될 겁니다.

바로 아래에 쓴

preorder_travel 함수는 return 하는 것이 아니고 key값을 출력하는 것이기 때문에 재귀적으로 들어가도 문제가 없이 작동됐고

이 함수를 참고해서 find함수를 만들었는데 find함수는 재귀적으로 들어갈때 return으로 나오지 못해서 None으로 나오는 것으로 이해했습니다

답변이 아니었으면 계속 헤맸겠네요

감사합니다