Alex Rivera | Logout

how to find the height of a node in binary tree recursively

Asked 2012-11-10T13:50:46.707
11
path = 0 # the lenght of the path
    while self.right != None or self.left != None:
        while self.right != None:
            self = self.right
            path = path +1 
        while self.left != None:
            self = self.left
            path = path +1
    return path

this is my sample code for find the Height, is defined as the length of the longest path by number of nodes from self to a leaf. The height of a leaf node is 1.

it doesn't work.

python algorithm binary-tree
Edit
Report

1 Answer

6

You were given the solution by mata, but I suggest you also look at your code and understand what it is doing:

    while self.right != None:
        self = self.right
        path = path +1

What will this do? it will find the right child, then its right child, and so on. So this checks only one path of the "rightmost" leaf.

This does the same for the left:

   while self.left != None:
        self = self.left
        path = path +1

The idea in recursion is that for each subproblem, you solve it using the exact same recipe for all other subproblems. So if you would apply your algorithm only to a subtree or a leaf, it would still work.

Also, a recursive definition calls itself (although you can implement this with a loop, but that is beyond the scope here).

Remeber the definition:

Recursion: see definition of Recursion.

;)

answered 2012-11-10T14:35:47.483

Your Answer