104. Maximum Depth of Binary Tree
Maximum Depth of Binary Tree (LeetCode 104) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.
How to solve Maximum Depth of Binary Tree
Maximum Depth of Binary Tree is a Postorder Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master postorder traversal for tree height, diameter, and path sum problems. Process children before root.
Work towards the solution in these steps:
- Think about how you can explore all nodes of the binary tree to find the maximum depth; traversal techniques like DFS or BFS are suitable here.
- Recursive traversal is a natural approach for trees; consider how you can use recursion to explore each subtree.
- In postorder traversal, you visit left and right children before processing the current node; how can this help in combining the depths of subtrees?
The reference solution runs in O(n) time and O(h) space.
The Maximum Depth of Binary Tree solution and editorial walks through the full approach with reference code.
Problem statement
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
Example 2:
Input: root = [1,null,2] Output: 2
Constraints:
- The number of nodes in the tree is in the range [0, 104].
- -100 <= Node.val <= 100
Topics and companies
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree.
Reported in interviews at LinkedIn, Amazon, Intel.
How to practise Maximum Depth of Binary Tree on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.
Open Maximum Depth of Binary Tree in the code editor, or read the Maximum Depth of Binary Tree editorial for a worked solution with its approach and complexity analysis.
Where Maximum Depth of Binary Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Postorder Traversal subpattern
- The full DSA patterns sheet
Problems related to Maximum Depth of Binary Tree
Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- All Nodes Distance K in Binary Tree — Medium, same subpattern
- Balanced Binary Tree — Easy, same subpattern
- Binary Tree Maximum Path Sum — Hard, same subpattern
- Binary Tree Postorder Traversal — Easy, same subpattern
- Delete Leaves With a Given Value — Medium, same subpattern
- Delete Nodes And Return Forest — Medium, same subpattern
Maximum Depth of Binary Tree FAQ
What is the LeetCode number of Maximum Depth of Binary Tree?
Maximum Depth of Binary Tree is LeetCode problem 104, rated Easy.
What pattern is used to solve Maximum Depth of Binary Tree?
Maximum Depth of Binary Tree is a Postorder Traversal problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.
What is the time complexity of Maximum Depth of Binary Tree?
The reference solution runs in O(n) time and O(h) space.
Which companies ask Maximum Depth of Binary Tree?
Maximum Depth of Binary Tree has been reported in interviews at LinkedIn, Amazon, Intel.