Language & Programming / LeetCode · Destination 6 of 6
Hard Problems
1 solution from leetcode_problems (trees_and_tries.py), shown as written. Open any entry to read the code.
2 entries
On this page: Problems LeetCode rates Hard, and attempts the source marks as only partly passing.
From l2mcgrat/leetcode_problems ↗ at commit f9cf5a8. Code is shown as written, test lines included; this site never runs it.
Every module, function and class is also listed in the source index.
Index
Trees and Tries · Binary Search Tree
Kth Largest Element in a Stream (11/12 cases passed, fails due to imbalanced BST)
class TreeNode:
def __init__(self, val, count, left=None, right=None):
self.val = val
self.count = count
self.left = left
self.right = right
class KthLargest:
def __init__(self, k, nums):
self.root = None
self.k = k
for num in nums:
self.root = self.insert(self.root, num)
def add(self, val: int) -> int:
self.root = self.insert(self.root, val)
return self.searchKth(self.root, self.k)
def insert(self, root, val):
if not root:
return TreeNode(val, 1)
if val > root.val:
root.right = self.insert(root.right, val)
else:
root.left = self.insert(root.left, val)
root.count += 1
return root
def searchKth(self, root, k):
m = root.right.count if root.right else 0
if k == m + 1:
return root.val
elif k <= m:
return self.searchKth(root.right, k)
else:
return self.searchKth(root.left, k - m - 1)