Python - Recursive count through BST

Question

Python - Recursive count through BST

Updated 2022-05-22

Viewed 2 times

python python-3.x binary-search-tree

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

score 0 · Answer 1 · 2022-05-22

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

never is assigned a different value, and
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

Python - Recursive count through BST

Related Questions

Java compile error for bounded typed ArrayList

best free offline TTS for python (mostly having indian accent in english)

Marklogic TDE columns with property values

my nn.sigmoid() gradient different with my manual calculation

Measure how long a React component is rendered

Going to channel where message is located

Why does my errorlevels don't list my echo messages in my batch script? They just list them all

Create a history /Log table based on status change

IProgress.Report delayed response

Can't install Cupy for CUDA 11.6

Popular Topics

Legal Stuff

Connect with us