BST: Kth Smallest Node (어려웠다ㅜ^ㅜ)

👩‍💻 문제

Given a binary search tree, find the kth smallest element in the tree. For example, if the tree contains the elements [1, 2, 3, 4, 5], the 3rd smallest element would be 3.

The solution to this problem usually involves traversing the tree in-order (left, root, right) and keeping track of the number of nodes visited until you find the kth smallest element. There are two main approaches to doing this:

Iterative approach using a stack: This approach involves maintaining a stack of nodes that still need to be visited, starting with the leftmost node. At each step, you pop a node off the stack, decrement the kth smallest counter, and check whether you have found the kth smallest element. If you have not, you continue traversing the tree by moving to the right child of the current node.

Recursive approach: This approach involves recursively traversing the tree in-order and keeping track of the number of nodes visited until you find the kth smallest element. You can use a helper function that takes a node and a value of k as input, and recursively calls itself on the left and right children of the node until it finds the kth smallest element.

Both of these approaches have their own advantages and disadvantages, and the best approach to use may depend on the specific problem constraints and the interviewer's preferences.

 

 

💡 풀이

    def kth_smallest(self, k):
        stack = []
        node = self.root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
                
            node = stack.pop()
            k -= 1 
            if k == 0:
                return node.value
                
            node = node.right

 

 

✍️ 해설

kth smallest 를 트리에서 찾는거다

트리는 기본적으로, 맨 왼쪽 아래가 가장 작은 수, 루트는 중간쯤 큰 수라는 점을 활용

전체를 in-order traverse하면 비효율적. * Time Complexity : O(n)

 

Space Complexity 도 O(n) 의 자리를 차지한다고 함.

 

굳이 모든 노드를 traverse할 필요 없이 k번 만큼만 하면 되니까, 루트 기준으로 왼쪽 자식트리만 먼저 끝내는 방식이다

 

위 코드에서 확인해보면,

while node에서 O(n) (inner loop)

오른쪽 subtree로 가는 과정 (pop부터) O(n)

 

* Why Not O(n^2)> ? 

while loop가 중첩돼있는데, 왜 n^2이 아닌가 하면,

outer loop는 그냥 단순히 stack이 존재하고 node가 존재할 경우라는 조건일 뿐이다.

그래서 outer loop한번당 inner loop가 도는 구조가 아니다.

 

outer loop는 단순히, 그냥 모든 노드가 방문돼야 한다는 조건을 걸고 있고, 

각 노드 존재하는 횟수인 상수 횟수로 고정되어 있는거다 

 

Each node is visited and processed once by the inner while loop and outer while loop combined.
The inner loop does not restart from the beginning for each iteration of the outer loop; 

it continues where it left off.

 

 

🥳 배운점

call stack 을 사용해서, pop하면서 그 value를 node에 저장하고, k의 카운트를 줄여가는 방식으로!

stack을 활용하는 방법을 더 잘 익혀야겠다 !