Finding the distance of a binary search tree from the root to a specific key

user_12846174 0
Viewed 57
def distance(self, rootOfTree, key):

    if rootOfTree is None:

        return -1

    totalDist = -1

    if rootOfTree.key is key:
        return totalDist + 1

    else:
        totalDist = self.distance(rootOfTree.left, key)

        if totalDist >= 0:

            return totalDist + 1

        totalDist = self.distance(rootOfTree.right, key)

        if totalDist >= 0:

            return totalDist + 1

    return totalDist

Hi i'm trying to code by using recursion by finding the distance from the root to a specific node given in the "key" parameter. But i can only managed to input two parameters in the function which is the root of my BST and the key which i want to find. Is it possible to just specify the "key" and traverse through the BST and find the "key" in the function

This is the 2nd part of my code

print("Depth:", bst.distance(root, "I"))

depth binary-search-tree recursion
1 Answers

The distance equals the depth you need to pursue in order to find the key node. You have to increase by one in each level, but only if that level contains the key.

class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

def distance(root, key):
    if root is None:
        return -1
    if root.data is key: # it's the key
        return 0
    else:
        dl = distance(root.left, key)
        dr = distance(root.right, key)
        if dl != -1:
           return 1 + dl
        elif dr != -1:
           return 1 + dr
        else: # both are -1
           return -1

For testing:

root = Tree()
root.data = "1"
root.left = Tree()
root.left.data = "2"
root.right = Tree()
root.right.data = "3"

root.left.left = Tree()
root.right.left = Tree()
root.left.right = Tree()
root.right.right = Tree()
root.left.left.data = "4"
root.left.right.data = "5"
root.right.left.data = "6"
root.right.right.data = "7"

distance(root, "1")
distance(root, "2")
distance(root, "3")
distance(root, "4")

Results: 

>>> distance(root, "1")
0
>>> distance(root, "2")
1
>>> distance(root, "3")
1
>>> distance(root, "4")
2
>>> distance(root, "7")
2
>>> distance(root, "8")
-1
user_76295600
Related