# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n#### ***Approach 1 (BFS)***\n1. The function takes a pointer to the root of a binary tree as input, represented by the `TreeNode` class. The goal is to find the largest values at each level of the tree.\n\n1. The function starts by checking if the `root` is a `nullptr` (i.e., an empty tree). If the tree is empty, it returns an empty vector, indicating that there are no largest values to find.\n\n1. If the tree is not empty, the function proceeds to find the largest values at each level.\n\n1. It initializes an empty vector `ans` to store the largest values and a `queue` queue for level-order traversal. The root node is pushed into the queue to start the traversal.\n\n1. The function enters a loop that continues until the queue is empty. Inside the loop, it processes one level of the tree at a time.\n\n1. For each level, it keeps track of the current level\'s length (the number of nodes in that level) and initializes `currMax` to the smallest possible integer value (`INT_MIN`) to find the largest value in that level.\n\n1. Another loop iterates through the nodes in the current level. It dequeues a node from the front of the queue and updates `currMax` if the value of the dequeued node is larger than the current maximum.\n\n1. For each dequeued node, if it has a left child, the left child is enqueued into the `queue`. If it has a right child, the right child is also enqueued.\n\n1. After processing all nodes in the current level, the largest value for that level (`currMax`) is added to the `ans` vector.\n\n1. The outer loop continues until all levels have been processed, and the `ans` vector contains the largest values for each level in the binary tree.\n\n1. Finally, the function returns the `ans` vector, which holds the largest values.\n\n# Complexity\n- *Time complexity:*\n $$O(n)$$\n \n\n- *Space complexity:*\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n vector largestValues(TreeNode* root) {\n if (root == nullptr) {\n return vector{};\n }\n \n vector ans;\n queue queue;\n queue.push(root);\n \n while (!queue.empty()) {\n int currentLength = queue.size();\n int currMax = INT_MIN;\n \n for (int i = 0; i < currentLength; i++) {\n TreeNode* node = queue.front();\n queue.pop();\n currMax = max(currMax, node->val);\n \n if (node->left) {\n queue.push(node->left);\n }\n \n if (node->right) {\n queue.push(node->right);\n }\n }\n \n ans.push_back(currMax);\n }\n \n return ans;\n }\n};\n\n```\n\n```C []\n\n#include \n#include \n#include \n\n// Definition for a binary tree node.\nstruct TreeNode {\n int val;\n struct TreeNode* left;\n struct TreeNode* right;\n};\n\n// Definition for a queue node.\nstruct QueueNode {\n struct TreeNode* treeNode;\n struct QueueNode* next;\n};\n\n// Definition for a queue.\nstruct Queue {\n struct QueueNode* front;\n struct QueueNode* rear;\n};\n\n// Initialize a new queue.\nstruct Queue* createQueue() {\n struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));\n queue->front = queue->rear = NULL;\n return queue;\n}\n\n// Enqueue a tree node in the queue.\nvoid enqueue(struct Queue* queue, struct TreeNode* treeNode) {\n struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));\n newNode->treeNode = treeNode;\n newNode->next = NULL;\n \n if (queue->rear == NULL) {\n queue->front = queue->rear = newNode;\n return;\n }\n \n queue->rear->next = newNode;\n queue->rear = newNode;\n}\n\n// Dequeue a tree node from the queue.\nstruct TreeNode* dequeue(struct Queue* queue) {\n if (queue->front == NULL) {\n return NULL;\n }\n \n struct TreeNode* treeNode = queue->front->treeNode;\n struct QueueNode* temp = queue->front;\n queue->front = queue->front->next;\n \n if (queue->front == NULL) {\n queue->rear = NULL;\n }\n \n free(temp);\n return treeNode;\n}\n\nint* largestValues(struct TreeNode* root, int* returnSize) {\n if (root == NULL) {\n *returnSize = 0;\n return NULL;\n }\n\n // Initialize the answer array and queue for level-order traversal.\n int* ans = (int*)malloc(sizeof(int) * 1000);\n struct Queue* queue = createQueue();\n enqueue(queue, root);\n\n int idx = 0; // Index to track the current position in the answer array.\n\n while (queue->front != NULL) {\n int currentLength = 0;\n int currMax = INT_MIN;\n\n // Process nodes at the current level.\n for (currentLength = queue->front != NULL; currentLength > 0; currentLength--) {\n struct TreeNode* node = dequeue(queue);\n currMax = (node->val > currMax) ? node->val : currMax;\n\n // Enqueue left and right children if they exist.\n if (node->left != NULL) {\n enqueue(queue, node->left);\n }\n if (node->right != NULL) {\n enqueue(queue, node->right);\n }\n }\n\n // Store the maximum value in the answer array.\n ans[idx] = currMax;\n idx++;\n }\n\n // Set the return size and return the answer array.\n *returnSize = idx;\n return ans;\n}\n\nint main() {\n // Create a sample binary tree for testing.\n struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n root->val = 1;\n root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n root->left->val = 3;\n root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n root->left->left->val = 5;\n root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n root->left->right->val = 3;\n root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n root->right->val = 2;\n root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n root->right->right->val = 9;\n\n int returnSize;\n int* result = largestValues(root, &returnSize);\n\n printf("Largest values at each level: ");\n for (int i = 0; i < returnSize; i++) {\n printf("%d ", result[i]);\n }\n printf("\\n");\n\n return 0;\n}\n\n\n```\n\n```Java []\nclass Solution {\n public List largestValues(TreeNode root) {\n if (root == null) {\n return new ArrayList();\n }\n \n List ans = new ArrayList();\n Queue queue = new LinkedList<>();\n queue.add(root);\n \n while (!queue.isEmpty()) {\n int currentLength = queue.size();\n int currMax = Integer.MIN_VALUE;\n \n for (int i = 0; i < currentLength; i++) {\n TreeNode node = queue.remove();\n currMax = Math.max(currMax, node.val);\n \n if (node.left != null) {\n queue.add(node.left);\n }\n \n if (node.right != null) {\n queue.add(node.right);\n }\n }\n \n ans.add(currMax);\n }\n \n return ans;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n if not root:\n return []\n \n ans = []\n queue = deque([root])\n \n while queue:\n current_length = len(queue)\n curr_max = float("-inf")\n \n for _ in range(current_length):\n node = queue.popleft()\n curr_max = max(curr_max, node.val)\n if node.left:\n queue.append(node.left)\n if node.right:\n queue.append(node.right)\n \n ans.append(curr_max)\n \n return ans\n\n```\n\n```javascript []\nfunction largestValues(root) {\n if (root === null) {\n return [];\n }\n \n const ans = [];\n const queue = [root];\n \n while (queue.length > 0) {\n const currentLength = queue.length;\n let currMax = -Infinity;\n \n for (let i = 0; i < currentLength; i++) {\n const node = queue.shift();\n currMax = Math.max(currMax, node.val);\n \n if (node.left) {\n queue.push(node.left);\n }\n \n if (node.right) {\n queue.push(node.right);\n }\n }\n \n ans.push(currMax);\n }\n \n return ans;\n}\n\n```\n\n\n---\n\n#### ***Approach 2 (DFS)***\n1. The `largestValues` function is the main entry point. It initializes an empty vector `ans` to store the largest values at each level and calls the `dfs` (depth-first search) function to traverse the binary tree.\n\n1. The `dfs` function is a recursive helper function. It takes two parameters: the current node and the depth of the current node.\n\n1. Inside the `dfs` function, it first checks if the current node is `nullptr`, indicating a leaf node or an empty subtree. If so, it returns without making any changes.\n\n1. If the depth is equal to the size of the `ans` vector, it means that we are at a new level in the tree. In this case, it pushes the value of the current node into the `ans` vector at the corresponding level.\n\n1. If the depth is not equal to the size of the `ans` vector, it means we have visited this level before. In this case, it updates the value at the corresponding level by taking the maximum of the existing value and the current node\'s value.\n\n1. The `dfs` function then makes two recursive calls to process the left and right children of the current node, incrementing the depth by 1 for each call.\n\n1. Once the `dfs` function completes its traversal, the `largestValues` function returns the `ans` vector, which contains the largest values at each level of the binary tree.\n\n# Complexity\n- *Time complexity:*\n $$O(n)$$\n \n\n- *Space complexity:*\n $$O(h)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n vector ans;\n \n vector largestValues(TreeNode* root) {\n dfs(root, 0);\n return ans;\n }\n \n void dfs(TreeNode* node, int depth) {\n if (node == nullptr) {\n return;\n }\n \n if (depth == ans.size()) {\n ans.push_back(node->val);\n } else {\n ans[depth] = max(ans[depth], node->val);\n }\n \n dfs(node->left, depth + 1);\n dfs(node->right, depth + 1);\n }\n};\n\n```\n\n```C []\n#include \n#include \n\n// Definition for a binary tree node.\nstruct TreeNode {\n int val;\n struct TreeNode* left;\n struct TreeNode* right;\n};\n\nint* ans;\nint ansSize = 0;\n\nvoid dfs(struct TreeNode* node, int depth) {\n if (node == NULL) {\n return;\n }\n\n if (depth == ansSize) {\n ans = (int*)realloc(ans, (ansSize + 1) * sizeof(int));\n ans[ansSize++] = node->val;\n } else {\n ans[depth] = (ans[depth] > node->val) ? ans[depth] : node->val;\n }\n\n dfs(node->left, depth + 1);\n dfs(node->right, depth + 1);\n}\n\nint* largestValues(struct TreeNode* root, int* returnSize) {\n ans = NULL;\n ansSize = 0;\n dfs(root, 0);\n *returnSize = ansSize;\n return ans;\n}\n\n\n\n```\n\n```Java []\nclass Solution {\n List ans;\n \n public List largestValues(TreeNode root) {\n ans = new ArrayList();\n dfs(root, 0);\n return ans;\n }\n \n public void dfs(TreeNode node, int depth) {\n if (node == null) {\n return;\n }\n \n if (depth == ans.size()) {\n ans.add(node.val);\n } else {\n ans.set(depth, Math.max(ans.get(depth), node.val));\n }\n \n dfs(node.left, depth + 1);\n dfs(node.right, depth + 1);\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n def dfs(node, depth):\n if not node:\n return\n \n if depth == len(ans):\n ans.append(node.val)\n else:\n ans[depth] = max(ans[depth], node.val)\n \n dfs(node.left, depth + 1)\n dfs(node.right, depth + 1)\n \n ans = []\n dfs(root, 0)\n return ans\n\n```\n\n```javascript []\n/**\n * Definition for a binary tree node.\n * function TreeNode(val) {\n * this.val = val;\n * this.left = this.right = null;\n * }\n */\n\n/**\n * @param {TreeNode} root\n * @return {number[]}\n */\nvar ans = [];\n\nvar largestValues = function(root) {\n dfs(root, 0);\n return ans;\n};\n\nvar dfs = function(node, depth) {\n if (node === null) {\n return;\n }\n\n if (depth === ans.length) {\n ans.push(node.val);\n } else {\n ans[depth] = Math.max(ans[depth], node.val);\n }\n\n dfs(node.left, depth + 1);\n dfs(node.right, depth + 1);\n};\n\n```\n\n\n---\n#### ***Approach 3 (DFS, Iterative)***\n1. The function `largestValues` takes the root of a binary tree as input and returns a vector of integers representing the largest values in each level.\n\n1. It checks if the root is `nullptr` (null). If the tree is empty, it returns an empty vector because there are no levels to process.\n\n1. It initializes an empty vector `ans` to store the largest values for each level.\n\n1. It uses a stack of pairs, where each pair contains a node from the tree and an integer representing its depth or level.\n\n1. It pushes the root node and level 0 into the stack as the starting point.\n\n1. It enters a loop that continues until the stack is empty. In each iteration:\n\n - It pops the top pair (node, depth) from the stack.\n\n - It checks if the `depth` is equal to the current size of the `ans` vector. If they are equal, this is the first node at this level, so it appends the node\'s value to the `ans` vector.\n\n - If the `depth` is not equal to the size of the `ans` vector, it means we\'ve already found a larger value for this level, so it compares the node\'s value with the existing value at that level and updates it if the current node\'s value is larger.\n\n - It then checks if the current node has left and right children. If it has a left child, it pushes that child into the stack with an increased depth. Similarly, if it has a right child, that child is pushed into the stack as well.\n\n1. The loop continues until all nodes at all levels are processed.\n\n1. Finally, it returns the `ans` vector, which contains the largest values for each level of the binary tree.\n\n# Complexity\n- *Time complexity:*\n $$O(n)$$\n \n\n- *Space complexity:*\n $$O(h)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n vector largestValues(TreeNode* root) {\n if (root == nullptr) {\n return vector{};\n }\n \n vector ans;\n stack> stack;\n stack.push(make_pair(root, 0));\n \n while (!stack.empty()) {\n pair pair = stack.top();\n stack.pop();\n TreeNode* node = pair.first;\n int depth = pair.second;\n \n if (depth == ans.size()) {\n ans.push_back(node->val);\n } else {\n ans[depth] = max(ans[depth], node->val);\n }\n \n if (node->left) {\n stack.push(make_pair(node->left, depth + 1));\n }\n \n if (node->right) {\n stack.push(make_pair(node->right, depth + 1));\n }\n }\n \n return ans;\n }\n};\n\n```\n\n```C []\n#include \n#include \n#include \n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n newNode->val = val;\n newNode->left = NULL;\n newNode->right = NULL;\n return newNode;\n}\n\nstruct TreeNode* insert(struct TreeNode* root, int val) {\n if (root == NULL) {\n return createNode(val);\n }\n\n if (val < root->val) {\n root->left = insert(root->left, val);\n } else if (val > root->val) {\n root->right = insert(root->right, val);\n }\n\n return root;\n}\n\nvoid freeTree(struct TreeNode* root) {\n if (root == NULL) {\n return;\n }\n\n freeTree(root->left);\n freeTree(root->right);\n free(root);\n}\n\ntypedef struct TreeNode TreeNode;\n\nint* largestValues(TreeNode* root, int* returnSize) {\n if (root == NULL) {\n *returnSize = 0;\n return NULL;\n }\n\n int* ans = (int*)malloc(sizeof(int) * 10000);\n int depth = 0;\n\n struct {\n TreeNode* node;\n int depth;\n } stack[10000];\n int top = -1;\n\n stack[++top] = (struct { TreeNode* node; int depth; }) {root, 0};\n\n while (top >= 0) {\n TreeNode* node = stack[top].node;\n depth = stack[top].depth;\n top--;\n\n if (depth == *returnSize) {\n ans[depth] = node->val;\n (*returnSize)++;\n } else {\n ans[depth] = (ans[depth] > node->val) ? ans[depth] : node->val;\n }\n\n if (node->left != NULL) {\n stack[++top] = (struct { TreeNode* node; int depth; }) {node->left, depth + 1};\n }\n\n if (node->right != NULL) {\n stack[++top] = (struct { TreeNode* node; int depth; }) {node->right, depth + 1};\n }\n }\n\n return ans;\n}\n\nint main() {\n TreeNode* root = createNode(1);\n root->left = createNode(3);\n root->right = createNode(2);\n root->left->left = createNode(5);\n root->left->right = createNode(3);\n root->right->right = createNode(9);\n\n int returnSize = 0;\n int* largest = largestValues(root, &returnSize);\n\n printf("Largest values in each level: ");\n for (int i = 0; i < returnSize; i++) {\n printf("%d ", largest[i]);\n }\n\n free(largest);\n freeTree(root);\n\n return 0;\n}\n\n\n\n```\n\n```Java []\nclass Solution {\n public List largestValues(TreeNode root) {\n if (root == null) {\n return new ArrayList();\n }\n \n List ans = new ArrayList<>();\n Stack> stack = new Stack<>();\n stack.push(new Pair<>(root, 0));\n \n while (!stack.isEmpty()) {\n Pair pair = stack.pop();\n TreeNode node = pair.getKey();\n int depth = pair.getValue();\n \n if (depth == ans.size()) {\n ans.add(node.val);\n } else {\n ans.set(depth, Math.max(ans.get(depth), node.val));\n }\n \n if (node.left != null) {\n stack.push(new Pair<>(node.left, depth + 1));\n }\n \n if (node.right != null) {\n stack.push(new Pair<>(node.right, depth + 1));\n }\n }\n \n return ans;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n if not root:\n return []\n \n ans = []\n stack = [(root, 0)]\n \n while stack:\n node, depth = stack.pop()\n if depth == len(ans):\n ans.append(node.val)\n else:\n ans[depth] = max(ans[depth], node.val)\n \n if node.left:\n stack.append((node.left, depth + 1))\n if node.right:\n stack.append((node.right, depth + 1))\n \n return ans\n\n```\n\n```javascript []\nvar largestValues = function(root) {\n if (root === null) {\n return [];\n }\n \n const ans = [];\n const stack = [[root, 0]];\n \n while (stack.length > 0) {\n const [node, depth] = stack.pop();\n \n if (depth === ans.length) {\n ans.push(node.val);\n } else {\n ans[depth] = Math.max(ans[depth], node.val);\n }\n \n if (node.left) {\n stack.push([node.left, depth + 1]);\n }\n \n if (node.right) {\n stack.push([node.right, depth + 1]);\n }\n }\n \n return ans;\n};\n\n```\n\n\n---\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---

Find Largest Value in Each Tree Row

Problem Description

Problem Description

Answer Panel