How to get the Maximum Depth of a Binary Tree in Python

0 min read 182 words

Let’s say that you have a binary tree and we needed to know it’s maximum depth.

Binary tree input data [3,9,20,null,null,15,7] could be visualised as follows:

    3
   / \
  9  20
    /  \
   15   7

In the above example, the depth would be 3. As there are 3 levels.

How would we write some Python code to work this out?

As usual, a TreeNode is defined as follows:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

As we need to loop through the same data types, this would be a perfect time to practice some recursion!

class Solution:
    def maxDepth(self, root):
        if root is None:
            return 0
            
        lDepth = self.maxDepth(root.left)
        rDepth = self.maxDepth(root.right)
        
        if lDepth > rDepth:
            return lDepth+1
        else:
            return rDepth+1

What we have done here, is return 0 if a node is empty, or doesn’t exist. Then we attempt to get the depth of both it’s left and right children.

At this point, we increment whichever is found and return that.

If you’re interested, you can practice this exercise on Leetcode over here: https://leetcode.com/problems/maximum-depth-of-binary-tree/

Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags