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

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:

```.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}```    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
```Code language: Python (python)```

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
```Code language: Python (python)```

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/

Subscribe
Notify of
1 Comment
Inline Feedbacks