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))
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.
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:
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.
1for each level of the tree and returns the longest (max) route to a leaf (a node with no children).get_heightis independent. Thusrootis a binding unique for each one. The recursion is treated the same way as any other function and thus you call theget_heighton the left and right child nodes (which is whatrootgets to be for those) and you get the two heights of the subtrees except your node so you add 1 to the highest. I have no idea why you expect a type error.maxreturns a number andget_heightreturns a number (0for the root case, or1 + max(x, y)otherwise), why would that be aTypeError?