Largest value in each level of Binary Tree

Given a binary tree, find the largest value in each level.

Examples :

Input :
        1
       / \
      2   3 
Output : 1 3

Input : 
        4
       / \
      9   2
     / \   \
    3   5   7 
Output : 4 9 7

Approach : The idea is to recursively traverse tree in a pre-order fashion. Root is considered to be at zeroth level. While traversing, keep track of the level of the element and if its current level is not equal to the number of elements present in the list, update the maximum element at that level in the list.

Below is the implementation to find largest value on each level of Binary Tree.

/* Recursive function to find

the largest value on each level */

void helper(vector<int>& res, Node* root, int d)

{

    if (!root)

        return;

 

    // Expand list size

    if (d == res.size())

        res.push_back(root->val);

 

    else

 

        // to ensure largest value

        // on level is being stored

        res[d] = max(res[d], root->val);

 

    // Recursively traverse left and

    // right subtrees in order to find

    // out the largest value on each level

    helper(res, root->left, d + 1);

    helper(res, root->right, d + 1);

}

 

// function to find largest values

vector<int> largestValues(Node* root)

{

    vector<int> res;

    helper(res, root, 0);

    return res;

}




Approach:  a recursive method have been discussed. In this post an iterative method has been discussed. The idea is to perform iterative level order traversal of the binary tree using queue. While traversing keep max variable which stores the maximum element of the current level of the tree being processed. When the level is completely traversed, print that max value.




void largestValueInEachLevel(Node* root)

{

    // if tree is empty

    if (!root)

        return;

 

    queue<Node*> q;

    int nc, max;

 

    // push root to the queue 'q'

    q.push(root);

 

    while (1) {

        // node count for the current level

        nc = q.size();

 

        // if true then all the nodes of

        // the tree have been traversed

        if (nc == 0)

            break;

 

        // maximum element for the current

        // level

        max = INT_MIN;

 

        while (nc--) {

 

            // get the front element from 'q'

            Node* front = q.front();

 

            // remove front element from 'q'

            q.pop();

 

            // if true, then update 'max'

            if (max < front->data)

                max = front->data;

 

            // if left child exists

            if (front->left)

                q.push(front->left);

 

            // if right child exists

            if (front->right)

                q.push(front->right);

        }

 

        // print maximum element of

        // current level

        cout << max << " ";

    }

}