How does getHeight recursively determine the height of a binary tree?

Question

I'm really not understanding the logic behind the code to compute the height of a binary tree. If someone understands it, can you explain it in a simple way?

I tried understanding by placing break points, but still the logic is unclear to me.

import pdb
class Node:
  def __init__(self,data):
      self.right=self.left=None
      self.data = data
      #print(self.data)
class Solution:  #creating and inserting the nodes
  def insert(self,root,data):
      #print(data)
      if root==None:
         return Node(data)
      else:
         if data<=root.data:
             cur=self.insert(root.left,data)
             root.left=cur
         else:
             cur=self.insert(root.right,data)
             root.right=cur
      return root
  def getHeight(self,root): #finding the height of the largest 
                               branchintree
    #Write your code here
    if not root:
        return -1
    if not root.left and not root.right:
        return 0
    left_height=self.getHeight(root.left)
    #print('left_height',left_height)
    right_height=self.getHeight(root.right)
    #print('right_height',right_height)
    r=max(left_height,right_height) + 1
    #print('r',r)
    return max(left_height,right_height) + 1




T=int(input())
pdb.set_trace()
myTree=Solution()
root=None
for i in range(T):
   data=int(input())
   root=myTree.insert(root,data)
height=myTree.getHeight(root)
print(height)

Answer 1

^{Note that the algorithm for finding the height of a tree is the same for binary search trees as well as general binary trees, so I will ignore BSTs for the purposes of this discussion.}

---

This code is not particularly clear, so I don't blame you for not understanding it.

Here's a re-write to cut through the noise:

from collections import namedtuple

Node = namedtuple("Node", "data left right")

def height(root): 
    return max(height(root.left), height(root.right)) + 1 if root else 0
    #      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^         ^^^^^^     
    #      |                                          |           |
    #      |                                          |           base case; root is None
    #      |                                          add the current node's height
    #      recursively find the maximum height of the current node's children


if __name__ == "__main__":
    """     1 
          /   \
         2     3
          \    /
           4  5
               \
                6 
    """
    root = Node(
        1,
        Node(
            2,
            None,
            Node(4, None, None)
        ),
        Node(
            3,
            Node(
                5,
                None,
                Node(6, None, None)
            ),
            None
        )
    )
    print(height(root)) # => 4

Now, we have two cases in a given call to height:

• root is None, in which case we return 0 because we have nothing. This is our base case, or condition that terminates the recursion.
• root is not None, in which case we return 1 to count the height of the current node under consideration by this particular recursive call plus the maximum of the height of the left and right subtrees rooted at the current node. This is the critical recursive step.

Let's walk through a call to height on the above example tree.

We first visit node {1} as our root. This isn't a base case, so {1} asks its left child {2} for its maximum height. {2} isn't a base case either, so it asks its left child, None, for its total. None is our first base case and returns 0 back to {2}. {2} then asks for the height of its right child, {4}. {4} is a leaf with two empty None references which return 0, but {4} adds 1 for itself and returns this to {2}.

Node {2} can now compute max(height(root.left), height(root.right)) which is max(0, 1) => 1, and {2} can add 1 to count its own height and report back to {1} its total of 2.

Our root {1} now has a height of 2 for its left subtree, but it hasn't checked its right subtree yet, so max(height(root.left), height(root.right)) has to wait.

The process is basically the same for the right subtree of {1}: if the node isn't a leaf node, it asks its children for their respective heights and takes the max, adding 1 to count itself, and reporting to the parent. In this case, {6} reports a height of 1 to {5}, {5} reports a height of 2 to {3} and {3} reports a height of 3 to {1}. At long last, {1} can compute max(2, 3) and add 1 for its own height, returning the final result of 4 to the caller.

If all of this is a bit abstract, you can always tool the recursive call to add a depth parameter and print its status.

from collections import namedtuple

Node = namedtuple("Node", "data left right")

def height(root, depth=0): 
    if root:
        print(" " * depth + f"{{{root.data}}} asking children...")
        left_height = height(root.left, depth + 4)
        right_height = height(root.right, depth + 4)
        ret = max(left_height, right_height) + 1
        print(" " * depth + f"{{{root.data}}} reporting max({left_height}, {right_height}) + 1 = {ret}")
        return ret

    print(" " * depth + "None returning 0")
    return 0


if __name__ == "__main__":
    """     1 
          /   \
         2     3
          \    /
           4  5
               \
                6 
    """
    root = Node(
        1,
        Node(
            2,
            None,
            Node(4, None, None)
        ),
        Node(
            3,
            Node(
                5,
                None,
                Node(6, None, None)
            ),
            None
        )
    )
    print(height(root)) # => 4

Output:

{1} asking children...
    {2} asking children...
        None returning 0
        {4} asking children...
            None returning 0
            None returning 0
        {4} reporting max(0, 0) + 1 = 1
    {2} reporting max(0, 1) + 1 = 2
    {3} asking children...
        {5} asking children...
            None returning 0
            {6} asking children...
                None returning 0
                None returning 0
            {6} reporting max(0, 0) + 1 = 1
        {5} reporting max(0, 1) + 1 = 2
        None returning 0
    {3} reporting max(2, 0) + 1 = 3
{1} reporting max(2, 3) + 1 = 4
4