CODEWITHSUNDEEP
pythonbinary-search-tree
sunny
sunny

Reputation: 125

Height of BST +1 more than expected

I made a function which determines the height of BST, but when the height of the tree is e.g. 2, the result that appears for me is 3, etc. I don't know what I should change in my code. If you need whole code to be able to answer me, tell me, so I'll copy it.

def maxDepth(self, node):
    if node is None:
        return 0

    else:

        # Compute the depth of each subtree
        lDepth = self.maxDepth(node.left)
        rDepth = self.maxDepth(node.right)

        # Use the larger one
        if (lDepth > rDepth):
            return lDepth + 1
        else:
            return rDepth + 1

Upvotes: 1

Views: 139

Answers (1)

Arty
Arty

Reputation: 16747

Instead of return 0 just do return -1 and you'll get desired height smaller by 1. Corrected code is below:

def maxDepth(self, node):
    if node is None:
        return -1
    else:
        # Compute the depth of each subtree
        lDepth = self.maxDepth(node.left)
        rDepth = self.maxDepth(node.right)

        # Use the larger one
        if (lDepth > rDepth):
            return lDepth + 1
        else:
            return rDepth + 1

Also you can use built-in max() function to make your code shorter:

def maxDepth(self, node):
    if node is None:
        return -1
    return max(self.maxDepth(node.left), self.maxDepth(node.right)) + 1

Note: OP is correct, height should be edge-based, i.e. tree with one node 5 should have height of 0. And empty tree (None-tree) has height -1. There are two proofs of this:

One proof in Wikipedia Tree Article says that height is edge based and Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

And another proof in famous book Cormen T.H. - Introduction to Algorithms:

enter image description here

Upvotes: 2

Related Questions