리트코드 - 700. Search in a Binary Search Tree

https://leetcode.com/problems/search-in-a-binary-search-tree/description/?envType=study-plan-v2&envId=leetcode-75

 

이진 검색 트리와 Value가 주어졌을 때, 해당 Val와 일치하는 노드를 찾을 경우 해당 노드가 루트인 하위 트리를 반환한다. 해당 노드가 존재하지 않으면 null을 반환한다.

 

이진 검색 트리의 특징은 루트 노드의 왼쪽은 값이 더 작은 노드, 오른 쪽에는 값이 더 큰 노드가 위치한다는 것이다.

 

이를 이용해서 재귀적으로 탐색을 진행하는 방식으로 문제를 해결할 수 있다.

 

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 현재 노드가 None이거나 값을 찾으면 반환
        if root is None or root.val == val: # O(1)
            return root

        # 찾는 값이 현재 노드의 값보다 작으면 왼쪽 하위 트리 검색
        elif val < root.val:
            return self.searchBST(root.left, val) # O(log n)

        # 찾는 값이 현재 노드의 값보다 크면 오른쪽 하위 트리 검색
        else:
            return self.searchBST(root.right, val) # O(log n)

 

 

균형 잡힌 BST의 경우 각 단계에서 탐색 범위가 절반으로 줄어든다. 따라서, 최악의 경우 탐색에 필요한 단계 수는 log₂n이 되어 시간 복잡도는 O(log n)이 된다

불균형 BST의 경우, 최악의 경우(트리가 한쪽으로 치우친 경우) 탐색 시간 복잡도는 O(n)이 될 수 있다.

 

재귀의 최대 깊이가 공간 복잡도에 직접적인 영향을 미친다.

균형 잡힌 트리의 경우, 재귀의 최대 깊이는 트리의 높이와 같으며, 이는 log₂n이다. 따라서, 공간 복잡도는 O(log n)이 된다.

최악의 경우(모든 노드가 하나의 브랜치에 있는 경우) 재귀의 깊이는 트리의 노드 수와 동일하므로, 공간 복잡도는 O(n)이 된다.