Leetcode 230 Kth Smallest Element in a BST

Soru

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Örnek 1

Input: root = [3,1,4,null,2], k = 1
Output: 1

Örnek 2

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Çözüm

• Soruda bir Binary Search Tree (BST) veriliyor ve bu ağaçta k. en küçük elemanı bulmamız isteniyor.
• Bu klasik bir Binary Search Tree (BST) sorusu ve inorder traversal mantığıyla çok güzel çözülüyor.
• BST’de:Sol alt ağaçtaki tüm değerler: küçük,Sağ alt ağaçtaki tüm değerler: büyük
• Bu yüzden:BST’nin inorder traversal sonucu: küçükten büyüğe sıralanmış bir liste verir.
• Hedefimiz:BST’yi inorder traversal ile gezmek ,k. sıradaki elemanı bulduğumuzda hemen sonucu döndürmek

Code

class Solution:
    def kthSmallest(self, root, k):
        self.count = 0
        self.result = None

        def inorder(node):
            if not node or self.result is not None:
                return
            
            inorder(node.left)
            
            # Düğüm ziyaret edildiğinde sayacı artır
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            
            inorder(node.right)
        
        inorder(root)
        return self.result

           
        

Comple

• Time complexity (Zaman Karmaşıklığı) : O(n) denilebilir.Aslında O(n+k) n ağacın yüksekliği
• Space complexity : O(n)