Find Largest Value in Each Tree Row

class Solution {
public:
    vector<int> findLargestValues(TreeNode* root) {
        if (!root) {
            return vector<int>();
        }
        
        vector<int> results;
        stack<pair<TreeNode*, int>> nodesStack;
        nodesStack.push({root, 0});
        
        while (!nodesStack.empty()) {
            auto current = nodesStack.top();
            nodesStack.pop();
            TreeNode* currentNode = current.first;
            int level = current.second;
            
            if (level == results.size()) {
                results.push_back(currentNode->val);
            } else {
                results[level] = max(results[level], currentNode->val);
            }
            
            if (currentNode->left) {
                nodesStack.push({currentNode->left, level + 1});
            }
            
            if (currentNode->right) {
                nodesStack.push({currentNode->right, level + 1});
            }
        }
        
        return results;
    }
};

The provided C++ program is designed to find the largest value on each level of a binary tree. The solution utilizes a depth-first search (DFS) approach leveraging a stack data structure to navigate through the tree nodes.

• At the beginning of the function, an initial check determines if the root pointer is nullptr. If true, the function returns an empty integer vector, indicating the tree has no nodes.
• An integer vector named results is used to store the maximum values of each tree level.
• A stack (nodesStack) is employed to manage pairs. Each pair consists of a TreeNode* and an integer representing the level of the tree node relative to the root.
• The root node and the level 0 (since it's the starting level) are pushed onto the stack as an initial pair.
• The stack is then processed in a loop until it becomes empty. Inside the loop:
  • The top element of the stack is retrieved and removed.
  • The current node and its level are extracted from this retrieved pair.
  • If the level of the current node matches the size of the results vector (indicating a new level is being explored), the node's value is added to results.
  • If not a new level, the value of the current node is compared with the existing value stored in results for that level, updating it to hold the maximum of the two.
• Child nodes of the current node (left and right, if they exist) are added to the stack along with their respective levels (current level + 1).
• Finally, the function returns the results vector containing the maximum values from each level of the tree.

This approach ensures that each tree row's largest value is identified and stored efficiently, with a complexity primarily dependent on the tree's size and structure.

class Solution {
    public List<Integer> maxValuesInEachRow(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        
        List<Integer> result = new ArrayList<>();
        Stack<Pair<TreeNode, Integer>> nodesStack = new Stack<>();
        nodesStack.push(new Pair<>(root, 0));
        
        while (!nodesStack.isEmpty()) {
            Pair<TreeNode, Integer> current = nodesStack.pop();
            TreeNode currentNode = current.getKey();
            int level = current.getValue();
            
            if (level == result.size()) {
                result.add(currentNode.val);
            } else {
                result.set(level, Math.max(result.get(level), currentNode.val));
            }
            
            if (currentNode.left != null) {
                nodesStack.push(new Pair<>(currentNode.left, level + 1));
            }
            
            if (currentNode.right != null) {
                nodesStack.push(new Pair<>(currentNode.right, level + 1));
            }
        }
        
        return result;
    }
}

The function maxValuesInEachRow implemented in Java is designed to find the largest value in each row of a binary tree. It returns these values as a list of integers. Consider the approach adopted in the solution:

• Check for an empty tree at the beginning and return an empty list if the tree has no nodes.
• Initialize a list result to store the maximum values of each level of the tree.
• Use a stack nodesStack to help in tree traversal. The stack stores pairs, where each pair contains a TreeNode and its associated level.
• Employ a while loop to process each node stored in the stack. Pop each pair from the stack, extract the TreeNode and its respective level.
• If the level of the TreeNode being processed matches the size of the result list (indicating the first node of that level), add its value to result. If not, update the existing value at that level in result with the maximum value between the current node and the previously recorded value.
• Push the left and right child nodes of the current node to the stack, with their respective levels incremented by one.

The algorithm ensures that each tree level is processed only once, and each level's maximum value is determined in a single traversal using a depth-first search mechanism. This method effectively handles the tree traversal and comparison of node values without requiring recursion, using a stack to manage the traversal state efficiently.

class Solution:
    def findMaxInLevels(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        results = []
        queue = [(root, 0)]
        
        while queue:
            current, level = queue.pop()
            if level == len(results):
                results.append(current.val)
            else:
                results[level] = max(results[level], current.val)
            
            if current.left:
                queue.append((current.left, level + 1))
            if current.right:
                queue.append((current.right, level + 1))
        
        return results

The provided Python code efficiently finds the largest value on each level of a binary tree using a breadth-first search approach. Here's a breakdown of how the solution is implemented:

• First, check if the root is None and return an empty list if true, which handles edge cases where the tree might be empty.
• Initialize a list results to store the maximum values of each tree level.
• Use a list queue as a queue to facilitate level-wise traversal of the tree, starting with the root node at level 0.
• Enter a while loop which continues until the queue is empty. Inside the loop:
  • Pop an element from the front of the queue, which contains the current node and its respective level.
  • Compare and update the maximum value for the current level. If it’s a new level (the current level equals the length of results), append the node value directly. Otherwise, update the maximum value for that level if the current node’s value is higher.
  • Add the current node's left and right children to the queue for subsequent processing, incrementing their level by 1.

The final output, results, contains the maximum values for each tree level in order of their depth in the tree, effectively solving the problem.