Find Largest Value in Each Tree Row - Practice Coding Problems

Find Largest Value in Each Tree Row - Problem

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Each row represents all nodes at the same level/depth in the tree. The result should contain the maximum value found at each level, starting from the root level (level 0) down to the deepest level.

Example: For a tree with root value 1, left child 3, and right child 2, where 3 has children 5 and 3, and 2 has child 9, the result would be [1, 3, 9] representing the maximum values at levels 0, 1, and 2 respectively.

Input & Output

Example 1 — Standard Binary Tree

$ Input: root = [1,3,2,5,3,null,9]

› Output: [1,3,9]

💡 Note: Level 0: Only node 1, max = 1. Level 1: Nodes 3 and 2, max = 3. Level 2: Nodes 5, 3, and 9, max = 9.

Example 2 — Single Node Tree

$ Input: root = [1]

› Output: [1]

💡 Note: Tree has only root node at level 0 with value 1.

Example 3 — Left-skewed Tree

$ Input: root = [5,4,null,3,null,null,null,2]

› Output: [5,4,3,2]

💡 Note: Each level has one node: 5 at level 0, 4 at level 1, 3 at level 2, 2 at level 3.

Constraints

The number of nodes in the tree will be in the range [1, 10⁴].
-2³¹ ≤ Node.val ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different levels

Level Analysis

Identify nodes at each level and find maximum

Result Array

Collect maximum values from each level

Key Takeaway

🎯 Key Insight: Use level-order traversal to naturally group nodes by tree rows, then track maximum at each level

Asked in

A Amazon 35 F Facebook 28 M Microsoft 22 G Google 18

The key insight is to process the tree level by level, tracking the maximum value at each level. The optimal approach uses BFS (breadth-first search) with a queue to naturally process nodes row by row. Time: O(n), Space: O(w) where w is the maximum width of the tree.

Common Approaches

Approach	Time	Space	Notes
✓ Level-Order Traversal (BFS)	O(n)	O(w)	Use breadth-first search to process nodes level by level, finding maximum at each level
DFS with Level Tracking	O(n)	O(h)	Use DFS to traverse all nodes while tracking current level and maximum at each level

Level-Order Traversal (BFS) — Algorithm Steps

Initialize queue with root node
For each level, process all current nodes in queue
Track maximum value at current level
Add children to queue for next level

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with root in queue, process level 0

Level Processing

Process all nodes at current level, track maximum

Next Level

Add children to queue, move to next level

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct QueueNode {
    struct TreeNode* treeNode;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
    int size;
};

struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    q->size = 0;
    return q;
}

void enqueue(struct Queue* q, struct TreeNode* node) {
    struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    temp->treeNode = node;
    temp->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = temp;
    } else {
        q->rear->next = temp;
        q->rear = temp;
    }
    q->size++;
}

struct TreeNode* dequeue(struct Queue* q) {
    if (q->front == NULL) return NULL;
    
    struct QueueNode* temp = q->front;
    struct TreeNode* node = temp->treeNode;
    q->front = q->front->next;
    
    if (q->front == NULL) q->rear = NULL;
    
    free(temp);
    q->size--;
    return node;
}

int* solution(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    
    int* result = (int*)malloc(1000 * sizeof(int));
    struct Queue* queue = createQueue();
    enqueue(queue, root);
    
    while (queue->size > 0) {
        int levelSize = queue->size;
        int levelMax = INT_MIN;
        
        // Process all nodes at current level
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = dequeue(queue);
            if (node->val > levelMax) {
                levelMax = node->val;
            }
            
            // Add children to queue for next level
            if (node->left) enqueue(queue, node->left);
            if (node->right) enqueue(queue, node->right);
        }
        
        result[(*returnSize)++] = levelMax;
    }
    
    free(queue);
    return result;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // For simplicity, create a test tree manually
    struct TreeNode* root = createNode(1);
    root->left = createNode(3);
    root->right = createNode(2);
    root->left->left = createNode(5);
    root->left->right = createNode(3);
    root->right->right = createNode(9);
    
    int returnSize;
    int* result = solution(root, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once where n is number of nodes

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum width of tree

✓ Linear Space

127.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Level-Order Traversal (BFS) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler