FilesExpand file tree

main

/

KthSmallestElementInaBST.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

74 lines (56 loc) · 1.89 KB

main

/

KthSmallestElementInaBST.py

Copy path

Top

File metadata and controls

• Code
• Blame

74 lines (56 loc) · 1.89 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

'''

230. Kth Smallest Element in a BST

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.

Example 1:

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

Output: 1

Example 2:

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

Output: 3

Constraints:

The number of nodes in the tree is n.

1 <= k <= n <= 104

0 <= Node.val <= 104

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

'''

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution(object):

'''

Recursive DFS: Time O(n) Space O(h)

We know that if we use in-order tree traversal, we know kth element is located at kth traversal position in in-order. Simply traverse the tree in-order and count the number of node to match with given k. We can return the node's value when k is equal to the count.

'''

# count = 0

# ans = TreeNode()

# def kthSmallest(self, root, k):

# def dfs(node):

# if node:

# dfs(node.left)

# self.count += 1

# if self.count == k:

# self.ans = node

# dfs(node.right)

# dfs(root)

# return self.ans.val

'''

Iterative DFS: Time O(n) Space O(h)

'''

def kthSmallest(self, root, k):

stack = []

count = 0

while True:

while root:

stack.append(root)

root = root.left

if not stack:

return -1

count += 1

root = stack.pop()

if count == k:

return root.val

root = root.right

return -1