How to Find Largest Value in Each Tree Row/Level using BFS or DFS Algorithm?

You need to find the largest value in each row of a binary tree.

Example:
Input:

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

This puzzle requires level-by-level traversal of a tree/binary tree, thus the algorithms used in How to Compute Average of Levels in Binary Tree? can be used exactly here.

However, each level does not have to be traversed by turns, as long as we know which level of the node we are currently dealing with. Generally speaking, we can use Depth First Search (DFS) or Breadth First Search (BFS) algorithms to solve the tree puzzles that require us to process nodes of different levels.

Compute the Maximum value for each Level of a Binary Tree using DFS

Using DFS, we process a path until we reach the leaves of the binary tree. Along the traversal path, we record the depth, hence using a hashmap or vector to remember the current maximum value for that level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> r;
        if (root == nullptr) return r;
        dfs(root, 1, r);
        return r;
    }
    
    void dfs(TreeNode* root, int depth, vector<int> &r) {
        if (root == nullptr) return;
        if (r.size() < depth) { // expand the vector for new depth
            r.push_back(root->val);
        };
        dfs(root->left, depth + 1, r);
        dfs(root->right, depth + 1, r);
        // update the current maximum for this level/depth
        r[depth - 1] = max(r[depth - 1], root->val); 
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> r;
        if (root == nullptr) return r;
        dfs(root, 1, r);
        return r;
    }
    
    void dfs(TreeNode* root, int depth, vector<int> &r) {
        if (root == nullptr) return;
        if (r.size() < depth) { // expand the vector for new depth
            r.push_back(root->val);
        };
        dfs(root->left, depth + 1, r);
        dfs(root->right, depth + 1, r);
        // update the current maximum for this level/depth
        r[depth - 1] = max(r[depth - 1], root->val); 
    }
};

The complexity is O(N) where each node of the binary tree is visited once. The space complexity is O(H) where H is the height of the binary tree, in worst case, the H will be equal to N when the tree is in fact a singly-directional link-list. The DFS is implemented using stack where this could be done via the recursion – compiler maintains a stack for you.

Compute the Maximum value for each Level of a Binary Tree using BFS

The BFS allows us to travel levels by levels. The implementation is based on a queue where we push the children nodes of the front of the queue at each iteration. The clever part using BFS is that the nodes in the queue belong to the same level, thus we can easily compute the maximum for the current level, and then push their children to the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> r;
        if (root == nullptr) return r;
        queue<TreeNode*> Q;
        Q.push(root);
        while (!Q.empty()) {
            int curMax = INT_MIN, t = Q.size();
            for (int i = 0; i < t; ++ i) { // these nodes belong to the same level
                auto p = Q.front();
                Q.pop();
                curMax = max(curMax, p->val);
                if (p->left) Q.push(p->left); // push next-evel node
                if (p->right) Q.push(p->right); // push next-evel node
            }
            r.push_back(curMax);
        }        
        return r;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> r;
        if (root == nullptr) return r;
        queue<TreeNode*> Q;
        Q.push(root);
        while (!Q.empty()) {
            int curMax = INT_MIN, t = Q.size();
            for (int i = 0; i < t; ++ i) { // these nodes belong to the same level
                auto p = Q.front();
                Q.pop();
                curMax = max(curMax, p->val);
                if (p->left) Q.push(p->left); // push next-evel node
                if (p->right) Q.push(p->right); // push next-evel node
            }
            r.push_back(curMax);
        }        
        return r;
    }
};

The complexity is O(N) and the space complexity is O(H) where H is the half of the N when the binary tree is complete.

–EOF (The Ultimate Computing & Technology Blog) —