Updated 2022-05-22
Viewed 2 times
0

so I am doing a Find Kth Largest Value in BST leetcode problem and I want to update the k_count every time I iterate through the tree. As you can see I print the tree value and the k_count everytime I go through. It works in that I am returning the value of the tree from largest value to smallest but I want the assocaited K_count with each tree node to update respectively. That is I want the largest value to have a k_count of 1 the second largest to have a k_count of 2 the third largest a k_count of 3 etc. I know I am close but getting thrown off with the recursive stack.

Any help with this would be greatly appreciated!

``````# This is an input class. Do not edit.
class BST:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def findKthLargestValueInBst(tree, k):
k_count = 0
result = 0
return findhelper(tree, k, k_count, result)

def findhelper(tree, k, k_count, result):

if tree is not None:

findhelper(tree.right, k, k_count, result)
print(tree.value)
print(k_count)
if k_count == k:
result = tree.value
findhelper(tree.left, k, k_count+1, result)

return result
``````
ðŸ”´ No definitive solution yet
ðŸ“Œ Solution 1

The main issue in your attempt is that `k_count` is a local variable that

1. never is assigned a different value, and
2. its value is never communicated back to the caller

More concretely, whatever the first recursive call does (to walk through the right subtree), that `print(k_count)` is always going to print the value of `k_count` it had before that recursive call was made, simply because that recursive call is not going to affect its value.

Again, each recursive execution of the function will get its own `k_count` variable, that is not related to any other `k_count` variable that exists in the call stack.

What you really want, is that when the first recursive call returns to the caller (and has visited the right subtree) that `k_count` will represent the number of nodes that were visited during that recursive call. But for that you would have to pass a reference to a single `k_count` attribute somewhere, or have the updated value returned by the recursive function.

But I would suggest to do this with a generator. It makes it so much easier to think about: perform a reversed inorder traversal using `yield`. Once you have that, just pull the first k values from that iterator and you're done.

Code:

``````def reversedInOrder(tree):
if tree:
yield from reversedInOrder(tree.right)
yield tree.value
yield from reversedInOrder(tree.left)

def findKthLargestValueInBst(tree, k):
for value in reversedInOrder(tree):
k -= 1
if k == 0:
return value
``````