Depth-First Search
Maximum Depth of Binary Tree
DESCRIPTION (inspired by Leetcode.com)
Given the root of a binary tree, write a recursive function to find its maximum depth, where maximum depth is defined as the number of nodes along the longest path from the root node down to a leaf node.
Example 1:
Input:
[4, 2, 7, 1, null, 6, 9, null, 8, null, null, null, null, null, null]
Output: 4 (The 4 nodes along the longest path are shown in bold)
Example 2:
Input:
[1, 2, 2, 3, 4, 4, 3]
Output: 3
Reading the input: the tree is given as a level-order array. Values are listed one level at a time, top to bottom and left to right, and null marks a missing child. In Example 2, 1 is the root, 2, 2 are its left and right children, and 3, 4, 4, 3 are the children of those two nodes, in order.
Explanation
- the maximum depth of the left subtree.
- the maximum depth of the right subtree.
Solution
class Solution:def maxDepth(self, root):if root is None:return 0# get the maximum depth of the left and right subtreesleft = self.maxDepth(root.left)right = self.maxDepth(root.right)return max(left, right) + 1
Animated Solution
def maxDepth(root):if root is None:return 0left = maxDepth(root.left)right = maxDepth(root.right)return max(left, right) + 1
max depth of binary tree
0 / 29
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N) where N is the number of nodes in the tree. We visit each node exactly once, and at each node, we perform constant time work.
Space Complexity: O(N) where N is the number of nodes. A total of N call frames have to be allocated, one for each node in the tree.
Your account is free and you can post anonymously if you choose.