CODEWITHSUNDEEP
pythonrecursionbinary-tree
fen
fen

Reputation: 91

Binary tree height - how does this algorithm work in python?

I came across this algorithm to find the height of a binary tree. Is anyone able to explain how it works? Specifically, I'm confused about the recursive calls inside the max function. What is max comparing on each iteration and how is the output able to be added to 1 without causing a TypeError? Thanks!

def get_height(root):
if root is None: 
    return 0
return 1 + max(get_height(root.left), get_height(root.right))

Upvotes: 1

Views: 2407

Answers (2)

abc
abc

Reputation: 11929

Adding some line to the code will help to figure out what's going on.
Here a class representing a Tree.

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

And a function to find the height.

def get_height(root):
    if root is None: 
        return 0

    my_height = 1 + max(get_height(root.left), get_height(root.right))
    print("id :{} height: {}".format(root.id,my_height))
    return my_height

t = Tree(1,Tree(2,Tree(4),Tree(5)),Tree(3))

t can be seen as follows.

     1
    / \
   2   3
  / \   
 4   5

When calling get_height(t) this is the output:

id :4 height: 1
id :5 height: 1
id :2 height: 2
id :3 height: 1
id :1 height: 3

The calls start from the root until after having reached a leaf node the function will be called with None.
Suppose to have reached a leaf (e.g., Node 4). The results on get_height() on Node 4 would be 1 + max(get_height(None),get_height(None)) = 1 + max(0,0) =1.
Node 4 thus returns 1. The caller (the parent of Node 4, i.e., Node 2) would get 1 from Node 4 and 1 from Node 5.
Thus it will conclude that its height is 1+max(1,1)=2 and return this value to the parent node.
In the same way, Node 1 (the root) would get 2 from Node 2 and 1 from Node 3 and compute its height as 1+max(1,2)=3.
The height of the Tree is 3, as the root as height 3.

Upvotes: 3

abarnert
abarnert

Reputation: 365717

Specifically, I'm confused about the recursive calls inside the max function. What is max comparing on each iteration and how is the output able to be added to 1 without causing a TypeError?

You’re calling a function twice, and passing the return values of those two function calls to max. So, max is comparing whatever this function returns.

If that isn’t clear, let’s break down that one-liner:

left_height = get_height(root.left)
right_height = get_height(root.right)
max_height = max(left_height, right_height)
return 1 + max_height

Since the function we’re calling always returns an integer, max is comparing two integers, which gives you the larger of the two integers. Which is something we can obviously add 1 to.

In other words, the height of the tree is 1 more than the height of whichever subtree is taller.

You may think I cheated there. How can I prove that the function always returns an integer, when I had to assume that to prove it?

The key is that recursion is inductive. If you don’t know much math, that’s a fancy way of saying this:

  • If the base case always returns an integer,
  • and recursion always calls a smaller case
  • and if we always return an integer as long as all smaller cases return an integer
  • then we always return an integer.

The first part is easy: if it’s None, we return 0.

The second part comes from the definition of a tree: the left branch of a tree and the right branch of a tree are always smaller subtrees of the tree. (This wouldn’t be true for a cyclic graph, where root.left could be root or its grandparent.)

The third part is the explanation from the first half of the answer.

And we’re done.

Upvotes: 2

Related Questions