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/