Updated 2022-05-22 1
Viewed 2 times

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)
        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.


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