CODEWITHSUNDEEP
pythonbinary-search-tree
Jackery Xu
Jackery Xu

Reputation: 402

get next highest value in BST

I wrote a function to get the next highest value in a binary search tree and return 0 if the input value is the highest in the tree:

def getNext(root, x):
if x > root.d:
    if root.r == None:
        return 0
    else:
        if x > root.r.d:
            getNext(root.r, x)
        else:
            temp = root.r

            while temp.l != None:
                temp = temp.l

            return temp.d
else:
    if root.l == None:
        return root.d
    elif x < root.l.d:
        getNext(root.l, x)
    else:
        temp = Node('')
        temp = root.l.r #53

        if temp.d > x:
            getNext(temp, x)
        else:
            while temp != None:
                if temp.r == None:
                    return root.d
                elif x > temp.r.d:
                    temp = temp.r
                else:
                    getNext(temp.r, x)
                    break

but it only returns None

I have tried adding a print before the return, and the print actually outputs correctly

Upvotes: 0

Views: 193

Answers (1)

Prajwal K R
Prajwal K R

Reputation: 672

Add a return before every recursive call, i.e.

return getNext(root.r,x)

return getNext(root.l,x)

return getNext(temp,x)

return getNext(temp.r,x)

Upvotes: 1

Related Questions