This is our solution and implementation to problem #515: Find Largest Value in Each Tree Row on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Find Largest Value in Each Tree Row on LeetCode.
Problem Analysis
Given the reference to the root node of a binary tree, we need to find the largest value in each row, or each depth, and store each largest value in a list. The 0th element will be the largest at depth 0, which is the root, the 1st element with the largest at depth 1, which are the child nodes of the root, the 2nd element will be the largest of the grandchildren of the root, etc. Our implementation should only visit each node once and should not use redundant space.
Implementation Strategy
We will implement the solution by performing a breadth first search starting from the provided root node. While traversing, we will keep track of the distance from the root node for each node. The algorithm can be summarized as:
- Create an empty list of integers maxResults.
- Create an empty Set to keep track of nodes we've visited.
- Create an empty Queue to keep track of nodes we've yet to visit. We'll also store the distance of each node from the root alongside the nodes themselves.
- While the queue is not empty:
- Dequeue and store the result into queueNode.
- If maxResults doesn't have an entry for queueNode.distanceFromRoot, add a new entry with queueNode.value.
- Otherwise, set the value to the max of queueNode.value and the value already in the list.
- If queueNode has a left child, add it to the queue with queueNode.distance + 1.
- If queueNode has a right child, add it to the queue with queueNode.distance + 1.
- Return maxResults.
Note: the same concept would also work with a depth-first search. We could use a Stack instead of a Queue to keep track of which nodes to visit next, or we could use a recursive implementation and pass in the distance as a method parameter.
Space and Time Complexity
This has a space complexity of O(1) if we don't include the output list itself, or O(n) if we do. The time complexity is O(n), as we visit each node one time.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.