kth_smallest_element_in_a_bst

View Source

 1from typing import Optional
 2from utils import TreeNode
 3from itertools import islice
 4
 5
 6# @leet start
 7class Solution:
 8    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
 9        """
10        We want to return the kth smallest element in a BST.
11        To do this, we can traverse the entire BST in order, and then stop at
12        the kth smallest element.
13        Since we traverse in order, we need to just see those k elements.
14
15        This solution does that, but turns it into an iterator, and then seeks to
16        the kth - 1 element and then returns that element.
17        """
18
19        def traverse(node):
20            if node:
21                yield from traverse(node.left)
22                yield node.val
23                yield from traverse(node.right)
24
25        return next(islice(traverse(root), k - 1, None))
26
27
28# @leet end
29
30
31def test():
32    assert 2 + 2 == 4

class Solution: View Source

 8class Solution:
 9    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
10        """
11        We want to return the kth smallest element in a BST.
12        To do this, we can traverse the entire BST in order, and then stop at
13        the kth smallest element.
14        Since we traverse in order, we need to just see those k elements.
15
16        This solution does that, but turns it into an iterator, and then seeks to
17        the kth - 1 element and then returns that element.
18        """
19
20        def traverse(node):
21            if node:
22                yield from traverse(node.left)
23                yield node.val
24                yield from traverse(node.right)
25
26        return next(islice(traverse(root), k - 1, None))

def kthSmallest(self, root: Optional[utils.TreeNode], k: int) -> int: View Source

 9    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
10        """
11        We want to return the kth smallest element in a BST.
12        To do this, we can traverse the entire BST in order, and then stop at
13        the kth smallest element.
14        Since we traverse in order, we need to just see those k elements.
15
16        This solution does that, but turns it into an iterator, and then seeks to
17        the kth - 1 element and then returns that element.
18        """
19
20        def traverse(node):
21            if node:
22                yield from traverse(node.left)
23                yield node.val
24                yield from traverse(node.right)
25
26        return next(islice(traverse(root), k - 1, None))

We want to return the kth smallest element in a BST. To do this, we can traverse the entire BST in order, and then stop at the kth smallest element. Since we traverse in order, we need to just see those k elements.

This solution does that, but turns it into an iterator, and then seeks to the kth - 1 element and then returns that element.

def test(): View Source

32def test():
33    assert 2 + 2 == 4