1161. Maximum Level Sum of a Binary Tree
Maximum Level Sum of a Binary Tree (LeetCode 1161) is a Medium 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 Level Order Traversal subpattern.
How to solve Maximum Level Sum of a Binary Tree
Maximum Level Sum of a Binary Tree is a Level Order Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master level order traversal using BFS. Solve zigzag, right side view, and level sum problems.
Work towards the solution in these steps:
- Calculate the sum for each level then find the level with the maximum sum.
- How can you traverse the tree ?
- How can you sum up the values for every level ?
The reference solution runs in O(n) time and O(h) space.
The Maximum Level Sum of a Binary Tree solution and editorial walks through the full approach with reference code.
Problem statement
Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.
Example 1:
Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.
Example 2:
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127] Output: 2
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- -105 <= Node.val <= 105
Topics and companies
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree.
Reported in interviews at Amazon, Facebook.
How to practise Maximum Level Sum of a 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 Level Sum of a Binary Tree in the code editor, or read the Maximum Level Sum of a Binary Tree editorial for a worked solution with its approach and complexity analysis.
Where Maximum Level Sum of a Binary Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Level Order Traversal subpattern
- The full DSA patterns sheet
Problems related to Maximum Level Sum of a Binary Tree
Other problems that use the same Level Order Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Level Order Traversal — Medium, same subpattern
- Binary Tree Right Side View — Medium, same subpattern
- Binary Tree Zigzag Level Order Traversal — Medium, same subpattern
- Find Largest Value in Each Tree Row — Medium, same subpattern
- All Nodes Distance K in Binary Tree — Medium, same pattern
- Balanced Binary Tree — Easy, same pattern
Maximum Level Sum of a Binary Tree FAQ
What is the LeetCode number of Maximum Level Sum of a Binary Tree?
Maximum Level Sum of a Binary Tree is LeetCode problem 1161, rated Medium.
What pattern is used to solve Maximum Level Sum of a Binary Tree?
Maximum Level Sum of a Binary Tree is a Level Order Traversal problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Level Order Traversal subpattern.
What is the time complexity of Maximum Level Sum of a Binary Tree?
The reference solution runs in O(n) time and O(h) space.
Which companies ask Maximum Level Sum of a Binary Tree?
Maximum Level Sum of a Binary Tree has been reported in interviews at Amazon, Facebook.