Level aggregates / views (Tree BFS Sub-pattern)
Fold each level into one answer: the last node, the max, the average, the width, or a check about two nodes on the same level.
- ›
"average / largest value of each level (row)"
- ›
"the nodes you can see from the right side"
- ›
"same depth but different parents"
- ›
"maximum width", counting the null gaps
Average of Levels sums in a long long (values reach 2³¹ − 1). Right Side View takes the last node of each round, which can come from the left subtree, so "just follow right children" is wrong. Largest Value per Row must start its max from a real value, since values can be negative. Cousins checks two things in one round: same level and different parents. Maximum Width numbers the nodes like a heap (2i+1, 2i+2) so the null gaps count, and re-bases the numbers each level so they don't overflow.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Average of Levels in Binary TreeWalkthroughEasyBasic Anchor·LeetCode #637
- 2Binary Tree Right Side ViewWalkthroughMediumBasic Reinforcement·LeetCode #199
- 3Find Largest Value in Each Tree RowWalkthroughMediumSlight Variation·LeetCode #515
- 4Cousins in Binary TreeWalkthroughEasyMedium·LeetCode #993
- 5Maximum Width of Binary TreeWalkthroughMediumInterview-Level·LeetCode #662
Template
// Per-level answers: the same rounds, but fold each level into one value.
// Here: the right side view (last node of each round) and the largest value per row.
vector<int> rightSideView(TreeNode* root) {
vector<int> view;
if (!root) return view;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
if (i == size - 1) view.push_back(node->val); // last in its round = seen from the right
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return view;
}
vector<int> largestValues(TreeNode* root) {
vector<int> best;
if (!root) return best;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
int mx = q.front()->val; // start from a real value, never 0
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
mx = max(mx, node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
best.push_back(mx);
}
return best;
}