CODEWITHSUNDEEP
pythonalgorithmsearchtreebinary-tree
Meiji Ishin
Meiji Ishin

Reputation: 43

Is this a good way to get the height of a binary tree?

I am not a CS student so this is not homework. I am trying to learn these things myself but I want to make sure I am not developing bad habits along the way.

Basically, I have a classic binary tree, and I want to calculate the height (or depth) of the tree.

What I mean by height is like this image:

this

The height of this tree is 3.

This is the python I came up with:

def height(node):

    #highest one of these two will be returned
    i_left = 0
    i_right = 0

    #if has left, increment and recursively move left
    if node.hasleft():
        i_left += height(node.left)
        i_left += 1

    #if has right, increment and recursively move right
    if node.hasright():
        i_right += height(node.right)
        i_right += 1

    #return the higher value
    if i_right <= i_left:
        return i_left    
    return i_right

This solution works, and I kinda like it because it's simple and doesn't have a lot of abstract things to work your head around. However, I do wonder if this is the way it should be done. Is there any way it could be improved, or is there a more accepted way of implementing a height function?

Upvotes: 2

Views: 1240

Answers (3)

kaya3
kaya3

Reputation: 51043

The key idea of your algorithm is sensible and correct; you have to make recursive calls on the left and right subtrees, and add 1.

Assuming your node.left and node.right attributes are None when there is no left or right subtree respectively, the function can be simplified by making just one check to see if the current node exists, instead of two checks to see if each of its children exist. This means the input is sometimes None, in which case the correct return value is -1 so that a leaf node's height will be 0.

def height(node):
    if node is None:
        return -1
    else:
        i_left = height(node.left)
        i_right = height(node.right)
        return 1 + max(i_left, i_right)

Or if you are a fan of one-liners:

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

This follows the usual definition of height as the number of edges in a longest path from the root, so that the height of a tree with one node is 0. If you define height as the number of nodes in that path, so that the height of a one-node tree is 1, then just change the base case to return 0 instead of return -1.

Upvotes: 4

bms
bms

Reputation: 46

Your overall algorithm is the best way to do it.

You have no way of knowing which branch will be the longest, so the only way to do it would be to check each path and find the maximum. Your recursive structure seems like a pretty classic one for a tree structure!

Upvotes: 0

Barmar
Barmar

Reputation: 781058

Your code only adds 1 to the height of the left or right nodes if there are child nodes. You need to add 1 for the current node even if there are no children. So it shouldn't be in the if blocks.

def height(node):

    #if has left, recursively move left
    if node.hasleft():
        i_left = height(node.left)
    else:
        i_left = 0

    #if has right, recursively move right
    if node.hasright():
        i_right = height(node.right)
    else:
        i_right = 0

    #return the higher value, plus 1 for the current node.
    return 1 + max(i_left, i_right)

Upvotes: 5

Related Questions