Why I can't get the shortest root to leaf height on BST?

Question

I wanted to get the shortest route to leaf node height on BST using Python 3. So, I write the code like this.

class Node:
    def __init__(self, key, value, left=None, right=None):
        self.key    = key
        self.value  = value
        self.left   = left
        self.right  = right

class BST:
    def __init__(self):
        self.root = None

    def get(self, key):
        self.get_item(self.root, key)

    def get_item(self, n, k):
        if n == None:
            return None
        if n.key > k:
            return self.get_item(n.left, k)
        elif n.key < k:
            return self.get_item(n.right, k)
        else:
            return n.value

    def put(self, key, value):
        self.root = self.put_item(self.root, key, value)

    def put_item(self, n, key, value):
        if n == None:
            return Node(key, value)
        if n.key > key:
            n.left = self.put_item(n.left, key, value)
        elif n.key < key:
            n.right = self.put_item(n.right, key, value)
        else:
            n.value = value
        return n

    def print_height(self):
        h = self.min_height(self.root)
        print(h)

    def short_height(self, root):
        if root == None:
            return 0
        return min(self.short_height(root.left), self.short_height(root.right)) +1

if __name__ == '__main__':
    t = BST()
    t.put(60, 'a')
    t.put(50, 'b')
    t.put(70, 'c')
    t.put(20, 'd')
    t.put(10, 'e')
    t.put(45, 'f')
    t.put(35, 'g')
    t.put(25, 'h')
    t.put(40, 'i')
    t.put(30, 'j')
    t.put(80, 'z')

t.print_height

Right result of print_height is '3', but I got the worng result '2'. (When I did't put the node(key:80, value:z), right result is '2', but this time I got '2')

To fix this problem, first, I changed the method 'short_height' like this. (To make sure that the code before +1 is well written)

    def short_height(self, root):
        if root == None:
            return 0
        return min(self.short_height(root.left), self.short_height(root.right)) +3

If it is normal, you should do +3 at height(not include root node) 2 of 80 and get 5 as a result, but since 6 came out, I confirmed that the code before +1 that was wrong.

I don't know how to fix this problem.

Answer 1

First some issues to make your code runnable:

• t.print_height does not call the method. You need to add parentheses
• The method print_height calls the method min_height, but there is no method with that name. I suppose you wanted to call short_height

The main issue is that your algorithm does not look for a leaf, but for a child that is None. This is not the same. Take for instance this simple tree:

                  3
                 /
                1

There is only one leaf, but your algorithm will find a short path from the root to its (non-existing) right child (None). But this path does not count, because it does not end in a leaf.

So alter your algorithm so that it uses the concept of leaf for the base case, i.e. a node that has no children, instead of itself being None.

Another remark: apparently, in your code challenge "height" is defined as the number of nodes on the path. The more common definition counts the number of edges on the path. This makes a difference of one. This is why I have used the term "levels" instead of "height" in the below solution, so to be clear that the number of nodes is counted:

    def short_levels(self):
        if self.root is None:
            return 0  # boundary case (empty tree)
        return self.short_levels_node(self.root)

    def short_levels_node(self, root):
        if not root.left and not root.right:  # It's a leaf
            return 1
        if not root.left:
            return self.short_levels_node(root.right) + 1
        if not root.right:
            return self.short_levels_node(root.left) + 1
        return min(self.short_levels_node(root.left), 
                   self.short_levels_node(root.right)) + 1

call as:

print(t.short_levels())