[hackerrank] Binary Search Tree : Lowest Common Ancestor (Python)

일단 이미지의 문제가 틀림

문제 (링크)

• 문제로 트리, value1, value2가 주어진다
• value1, value2가 가지고 있는 공통의 부모 노드 중에 가장 낮은 (루트로부터 멀리 떨어진, depth가 깊은) 노드를 반환해야 한다
• 위 이미지의 노드 4는 노드 5 밑에 들어가있어야 되는데.. 찾아보니 오류가 맞는 것 같다

풀이

def lca(root, v1, v2):   
  if v1>v2:
    v1, v2 = v2, v1 # set the v2 for smaller number
    
  curr = root
  if (curr.info >=v1) & (curr.info <=v2): # v1<curr<v2 is answer
    return curr
  elif (curr.info <v1)&(curr.right is not None):
    return lca(curr.right, v1, v2)
  elif (curr.info >v2)&(curr.left is not None):
    return lca(curr.left, v1, v2)

 처음에는 자식 노드에서 타고 올라가면서 가장 먼저 겹치는 숫자를 탐지하면 되지 않을까? 하는 생각이 들었는데 주어진 함수의 입력값이 root 노드라서 생각을 고쳤다. (문제를 잘 읽자.) 

 value1, value2 노드의 부모 노드는 해당 노드의 두 숫자 사이의 값을 가질 것이다. 따라서 v1이 무조건 더 작은 값을 가지도록 설정해주고, 주어진 루트 노드의 값이 v1보다 작으면 오른쪽 노드로, v2보다  크면 왼쪽 노드로 이동해서 다시 재귀함수로 동작하게 해주었다.

 내가 이 문제를 30분이나 고생한 이유는 if 에만 리턴을 해주고 elif 두 줄에는 리턴을 안해줘서 재귀함수를 빠져나오는 길에 None이 반환시켜버렸기 때문이다. 기본기를 탄탄히 해야한다는 모 강사님의 말이 떠오르는 날이다.