Count Good Nodes in Binary Tree

🎯

Count Good Nodes in Binary Tree

mediumTREEAmazonGoogleFacebook

Imagine you are analyzing a network of sensors arranged in a tree structure, and you want to count how many sensors have readings that are the highest seen so far on the path from the root sensor.

💡 This problem involves traversing a binary tree while keeping track of the maximum value seen on the path from the root to the current node. Beginners often struggle because it requires carrying state information during traversal and understanding how to compare node values relative to ancestors.

📋

Problem Statement

Given a binary tree where each node contains an integer value, a node X in the tree is named 'good' if in the path from the root to X there are no nodes with a value greater than X's value. Return the number of good nodes in the binary tree.

The number of nodes in the binary tree is in the range [1, 10^5].Each node's value is an integer in the range [-10^4, 10^4].

💡

Example

Input"root = [3,1,4,3,null,1,5]"

Output4

The good nodes are 3 (root), 4, 5, and the left child 3 of node 1. Each of these nodes is greater than or equal to all nodes on the path from the root.

• Single node tree → output is 1
• All nodes have the same value → output equals total nodes
• Strictly decreasing values from root → output is 1
• Tree with negative values → count good nodes correctly

⚠️

Common Mistakes

Not updating max value correctly when traversing children

Incorrect count of good nodes, missing some nodes that should be counted

✅ Always update max_val = max(max_val, node.val) before recursive calls or pushing children

Counting nodes that are strictly greater instead of greater or equal

Under-counting good nodes, especially when node values are equal to max_val

✅ Use >= comparison instead of > when checking if node is good

Using BFS without carrying max_val state with each node

Incorrect results because max_val is not tracked per path

✅ Store max_val along with each node in the queue

Not handling null root input

Runtime error or incorrect output

✅ Check if root is null and return 0 immediately

🧠

Brute Force (Pure Recursion with Path Tracking)

💡 This approach introduces the fundamental idea of traversing the tree and checking conditions at each node without any optimization. It helps beginners understand the problem deeply before moving to more efficient methods.

Intuition

Traverse the tree from the root to each node, keeping track of the maximum value seen so far on the path. For each node, compare its value with the maximum and count it if it is greater or equal.

Algorithm

1. Start at the root node with the initial max value as the root's value.
2. At each node, compare the node's value with the max value passed from its parent.
3. If the node's value is greater or equal, increment the count of good nodes.
4. Recursively traverse left and right children, updating the max value accordingly.

💡 The challenge is to maintain the max value seen so far on the path and correctly update it for each recursive call.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_good_nodes(root):
    def dfs(node, max_val):
        if not node:
            return 0
        count = 1 if node.val >= max_val else 0
        max_val = max(max_val, node.val)
        count += dfs(node.left, max_val)
        count += dfs(node.right, max_val)
        return count
    return dfs(root, root.val)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1, TreeNode(3))
    root.right = TreeNode(4, TreeNode(1), TreeNode(5))
    print(count_good_nodes(root))  # Output: 4

Line Notes

def dfs(node, max_val):Defines a helper function to traverse nodes recursively with max_val tracking

if not node:Base case: if node is None, no good nodes here

count = 1 if node.val >= max_val else 0Count current node if it meets the good node condition

max_val = max(max_val, node.val)Update max_val to carry forward the highest value seen so far

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int countGoodNodes(TreeNode root) {
        return dfs(root, root.val);
    }
    private int dfs(TreeNode node, int maxVal) {
        if (node == null) return 0;
        int count = node.val >= maxVal ? 1 : 0;
        maxVal = Math.max(maxVal, node.val);
        count += dfs(node.left, maxVal);
        count += dfs(node.right, maxVal);
        return count;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(3);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(5);
        Solution sol = new Solution();
        System.out.println(sol.countGoodNodes(root)); // Output: 4
    }
}

Line Notes

private int dfs(TreeNode node, int maxVal) {Helper method for recursive traversal with maxVal tracking

if (node == null) return 0;Base case: no node means no good nodes

int count = node.val >= maxVal ? 1 : 0;Count current node if it qualifies as good

maxVal = Math.max(maxVal, node.val);Update maxVal for children traversal

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int countGoodNodes(TreeNode* root) {
        return dfs(root, root->val);
    }
private:
    int dfs(TreeNode* node, int maxVal) {
        if (!node) return 0;
        int count = (node->val >= maxVal) ? 1 : 0;
        maxVal = max(maxVal, node->val);
        count += dfs(node->left, maxVal);
        count += dfs(node->right, maxVal);
        return count;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->left->left = new TreeNode(3);
    root->right = new TreeNode(4);
    root->right->left = new TreeNode(1);
    root->right->right = new TreeNode(5);
    Solution sol;
    cout << sol.countGoodNodes(root) << endl; // Output: 4
    return 0;
}

Line Notes

int dfs(TreeNode* node, int maxVal) {Recursive helper to traverse tree with maxVal tracking

if (!node) return 0;Base case: null node means no good nodes

int count = (node->val >= maxVal) ? 1 : 0;Count current node if it is good

maxVal = max(maxVal, node->val);Update maxVal for recursive calls

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function countGoodNodes(root) {
    function dfs(node, maxVal) {
        if (!node) return 0;
        let count = node.val >= maxVal ? 1 : 0;
        maxVal = Math.max(maxVal, node.val);
        count += dfs(node.left, maxVal);
        count += dfs(node.right, maxVal);
        return count;
    }
    return dfs(root, root.val);
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(1, new TreeNode(3)),
    new TreeNode(4, new TreeNode(1), new TreeNode(5))
);
console.log(countGoodNodes(root)); // Output: 4

Line Notes

function dfs(node, maxVal) {Recursive helper function with maxVal parameter

if (!node) return 0;Base case: no node means no good nodes

let count = node.val >= maxVal ? 1 : 0;Count current node if it meets good node criteria

maxVal = Math.max(maxVal, node.val);Update maxVal for children traversal

⏱

Complexity

TimeO(n)

SpaceO(h)

We visit each node once, so time is O(n). The recursion stack can go as deep as the height h of the tree, so space is O(h).

💡 For a tree with 100,000 nodes, this means about 100,000 operations and stack depth up to the tree height, which is efficient for balanced trees.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and is the standard solution for this problem.

🧠

Iterative BFS with Queue and Max Tracking

💡 This approach uses breadth-first search to traverse the tree level by level, carrying the max value seen on the path to each node. It helps understand BFS traversal with state propagation.

Intuition

Use a queue to traverse nodes level by level. Along with each node, store the max value seen on the path from the root. Count nodes whose value is at least the max value.

Algorithm

1. Initialize a queue with the root node and its value as the current max.
2. While the queue is not empty, dequeue a node and its max value.
3. If the node's value is greater or equal to the max, increment the count.
4. Enqueue the children with updated max values.

💡 The key is to carry the max value along with each node in the queue to maintain correct state during BFS.

</>

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_good_nodes(root):
    if not root:
        return 0
    count = 0
    queue = deque([(root, root.val)])
    while queue:
        node, max_val = queue.popleft()
        if node.val >= max_val:
            count += 1
        max_val = max(max_val, node.val)
        if node.left:
            queue.append((node.left, max_val))
        if node.right:
            queue.append((node.right, max_val))
    return count

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1, TreeNode(3))
    root.right = TreeNode(4, TreeNode(1), TreeNode(5))
    print(count_good_nodes(root))  # Output: 4

Line Notes

queue = deque([(root, root.val)])Initialize queue with root and its value as max_val

while queue:Process nodes level by level until queue is empty

node, max_val = queue.popleft()Extract current node and max_val for this path

if node.val >= max_val:Check if current node is a good node

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int countGoodNodes(TreeNode root) {
        if (root == null) return 0;
        int count = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, root.val));
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            TreeNode node = p.getKey();
            int maxVal = p.getValue();
            if (node.val >= maxVal) count++;
            maxVal = Math.max(maxVal, node.val);
            if (node.left != null) queue.offer(new Pair<>(node.left, maxVal));
            if (node.right != null) queue.offer(new Pair<>(node.right, maxVal));
        }
        return count;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(3);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(5);
        Solution sol = new Solution();
        System.out.println(sol.countGoodNodes(root)); // Output: 4
    }
}

// Note: Use javafx.util.Pair or define your own Pair class if javafx is unavailable.

Line Notes

Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();Queue stores nodes with their maxVal on path

queue.offer(new Pair<>(root, root.val));Start BFS with root and its value as maxVal

Pair<TreeNode, Integer> p = queue.poll();Dequeue node and maxVal for processing

if (node.val >= maxVal) count++;Count node if it is good

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int countGoodNodes(TreeNode* root) {
        if (!root) return 0;
        int count = 0;
        queue<pair<TreeNode*, int>> q;
        q.push({root, root->val});
        while (!q.empty()) {
            auto [node, maxVal] = q.front(); q.pop();
            if (node->val >= maxVal) count++;
            maxVal = max(maxVal, node->val);
            if (node->left) q.push({node->left, maxVal});
            if (node->right) q.push({node->right, maxVal});
        }
        return count;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->left->left = new TreeNode(3);
    root->right = new TreeNode(4);
    root->right->left = new TreeNode(1);
    root->right->right = new TreeNode(5);
    Solution sol;
    cout << sol.countGoodNodes(root) << endl; // Output: 4
    return 0;
}

Line Notes

queue<pair<TreeNode*, int>> q;Queue holds nodes paired with maxVal on path

q.push({root, root->val});Initialize BFS with root node and its value

auto [node, maxVal] = q.front(); q.pop();Extract current node and maxVal

if (node->val >= maxVal) count++;Count node if it qualifies as good

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function countGoodNodes(root) {
    if (!root) return 0;
    let count = 0;
    const queue = [[root, root.val]];
    while (queue.length > 0) {
        const [node, maxVal] = queue.shift();
        if (node.val >= maxVal) count++;
        const newMax = Math.max(maxVal, node.val);
        if (node.left) queue.push([node.left, newMax]);
        if (node.right) queue.push([node.right, newMax]);
    }
    return count;
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(1, new TreeNode(3)),
    new TreeNode(4, new TreeNode(1), new TreeNode(5))
);
console.log(countGoodNodes(root)); // Output: 4

Line Notes

const queue = [[root, root.val]];Initialize queue with root and its value as maxVal

while (queue.length > 0) {Process nodes until queue is empty

const [node, maxVal] = queue.shift();Dequeue node and maxVal for processing

if (node.val >= maxVal) count++;Count node if it is a good node

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once. The queue can hold up to O(n) nodes in the worst case (e.g., a complete binary tree).

💡 For 100,000 nodes, this means 100,000 operations and potentially storing many nodes in the queue at once.

Interview Verdict: Accepted

This approach is equally efficient as recursion but uses explicit queue management, which some candidates prefer.

🧠

DFS with Explicit Stack (Iterative Preorder Traversal)

💡 This approach simulates recursion using an explicit stack to avoid recursion depth issues and to practice iterative tree traversal with state tracking.

Intuition

Use a stack to traverse the tree in preorder. Along with each node, store the max value seen so far. Count nodes that are good as you pop them from the stack.

Algorithm

1. Initialize a stack with the root node and its value as maxVal.
2. While the stack is not empty, pop a node and its maxVal.
3. If the node's value is at least maxVal, increment count.
4. Push the right and left children onto the stack with updated maxVal.

💡 The order of pushing right then left ensures preorder traversal order, and maxVal is updated for each child.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_good_nodes(root):
    if not root:
        return 0
    count = 0
    stack = [(root, root.val)]
    while stack:
        node, max_val = stack.pop()
        if node.val >= max_val:
            count += 1
        max_val = max(max_val, node.val)
        if node.right:
            stack.append((node.right, max_val))
        if node.left:
            stack.append((node.left, max_val))
    return count

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1, TreeNode(3))
    root.right = TreeNode(4, TreeNode(1), TreeNode(5))
    print(count_good_nodes(root))  # Output: 4

Line Notes

stack = [(root, root.val)]Initialize stack with root and its value as maxVal

while stack:Process nodes until stack is empty

node, max_val = stack.pop()Pop current node and maxVal for processing

if node.val >= max_val:Count node if it qualifies as good

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int countGoodNodes(TreeNode root) {
        if (root == null) return 0;
        int count = 0;
        Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
        stack.push(new Pair<>(root, root.val));
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> p = stack.pop();
            TreeNode node = p.getKey();
            int maxVal = p.getValue();
            if (node.val >= maxVal) count++;
            maxVal = Math.max(maxVal, node.val);
            if (node.right != null) stack.push(new Pair<>(node.right, maxVal));
            if (node.left != null) stack.push(new Pair<>(node.left, maxVal));
        }
        return count;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(3);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(5);
        Solution sol = new Solution();
        System.out.println(sol.countGoodNodes(root)); // Output: 4
    }
}

// Note: Use javafx.util.Pair or define your own Pair class if javafx is unavailable.

Line Notes

Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();Stack stores nodes with maxVal for iterative DFS

stack.push(new Pair<>(root, root.val));Start with root node and its value

Pair<TreeNode, Integer> p = stack.pop();Pop node and maxVal for processing

if (node.val >= maxVal) count++;Count node if it is good

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int countGoodNodes(TreeNode* root) {
        if (!root) return 0;
        int count = 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push({root, root->val});
        while (!stk.empty()) {
            auto [node, maxVal] = stk.top(); stk.pop();
            if (node->val >= maxVal) count++;
            maxVal = max(maxVal, node->val);
            if (node->right) stk.push({node->right, maxVal});
            if (node->left) stk.push({node->left, maxVal});
        }
        return count;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->left->left = new TreeNode(3);
    root->right = new TreeNode(4);
    root->right->left = new TreeNode(1);
    root->right->right = new TreeNode(5);
    Solution sol;
    cout << sol.countGoodNodes(root) << endl; // Output: 4
    return 0;
}

Line Notes

stack<pair<TreeNode*, int>> stk;Stack holds nodes with maxVal for iterative DFS

stk.push({root, root->val});Initialize stack with root node and its value

auto [node, maxVal] = stk.top(); stk.pop();Pop node and maxVal for processing

if (node->val >= maxVal) count++;Count node if it is good

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function countGoodNodes(root) {
    if (!root) return 0;
    let count = 0;
    const stack = [[root, root.val]];
    while (stack.length > 0) {
        const [node, maxVal] = stack.pop();
        if (node.val >= maxVal) count++;
        const newMax = Math.max(maxVal, node.val);
        if (node.right) stack.push([node.right, newMax]);
        if (node.left) stack.push([node.left, newMax]);
    }
    return count;
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(1, new TreeNode(3)),
    new TreeNode(4, new TreeNode(1), new TreeNode(5))
);
console.log(countGoodNodes(root)); // Output: 4

Line Notes

const stack = [[root, root.val]];Initialize stack with root and its value as maxVal

while (stack.length > 0) {Process nodes until stack is empty

const [node, maxVal] = stack.pop();Pop node and maxVal for processing

if (node.val >= maxVal) count++;Count node if it is a good node

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once. The stack size is at most the height of the tree, O(h).

💡 For a balanced tree with 100,000 nodes, the height is about 17, so stack space is small compared to total nodes.

Interview Verdict: Accepted

This approach avoids recursion depth issues and is useful in languages with limited recursion stack.

📊

All Approaches - One-Glance Tradeoffs

💡 The recursive DFS approach is the simplest and most common to code in interviews. BFS and iterative DFS are alternatives useful in specific scenarios like avoiding recursion limits.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive DFS)	O(n)	O(h)	Yes (deep recursion)	N/A	Code this approach in 95% of interviews
2. Iterative BFS with Queue	O(n)	O(n)	No	N/A	Mention as alternative; code if asked for BFS
3. Iterative DFS with Stack	O(n)	O(h)	No	N/A	Mention if recursion depth is a concern

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly during interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force recursive approach to demonstrate understanding.Discuss iterative BFS and DFS approaches as alternatives.Write clean, correct code for the chosen approach.Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, state tracking during traversal, and your ability to write clean, bug-free code that handles edge cases.

Common Follow-ups

• What if the tree is very deep? → Use iterative DFS to avoid stack overflow.
• Can you solve it using BFS? → Yes, by storing max values in the queue.

💡 These follow-ups check your flexibility with traversal methods and handling large input constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree traversal, 2) Need to track max/min value on path, 3) Counting or filtering nodes based on path properties, 4) Requires state propagation during traversal.

Signature Phrases

'no nodes with a value greater than X's value on the path from root to X''count nodes that satisfy a condition relative to ancestors'

NOT This Pattern When

Problems that only require simple traversal without path state, or those that use DP on trees rather than BFS/DFS with state.

Similar Problems

Binary Tree Cameras - also uses DFS with state trackingBinary Tree Maximum Path Sum - tracks max sums on pathsLongest Univalue Path - tracks path properties during traversal

Practice

1. You need to find the value of the leftmost node at the deepest level of a binary tree. Which approach guarantees an optimal solution that efficiently finds this value without traversing unnecessary nodes multiple times?

easy

A. Breadth-first search (BFS) level order traversal inserting right child before left child to ensure the last node processed is the bottom-left node.

B. Depth-first search (DFS) that tracks the maximum depth and updates the leftmost node when a deeper level is found.

C. Greedy traversal always choosing the left child first until reaching the deepest node.

D. Dynamic programming storing results of subtrees to combine leftmost values at each depth.

Solution

1. Step 1: Understand problem goal

   The problem requires finding the bottom-left value, which is the leftmost node at the deepest level.

2. Step 2: Analyze BFS approach with right-to-left insertion

   BFS with queue inserting right child before left child ensures the last node popped is the bottom-left node, but this approach requires careful enqueue order and may be less intuitive.

3. Step 3: Analyze DFS approach

   DFS that tracks maximum depth and updates the leftmost node when a deeper level is found directly finds the bottom-left node efficiently without relying on enqueue order.

4. Step 4: Choose optimal approach

   DFS approach is simpler and guarantees correct bottom-left node without tricky enqueue order.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   DFS tracking max depth and leftmost node is a standard, efficient solution [OK]

Hint: DFS tracking max depth and leftmost node efficiently finds bottom-left node [OK]

Common Mistakes:

• Assuming BFS with right-to-left insertion is always simpler
• Thinking greedy left child traversal always finds bottom-left
• Misapplying DP to this problem

2. You are given a tree where each node can have multiple children. You need to collect the values of nodes level by level, starting from the root, and return them as a list of lists. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting nodes with the highest value at each level

B. Depth-first search (DFS) with backtracking to collect nodes at each depth

C. Dynamic programming to store and reuse subtree results

D. Breadth-first search (BFS) using a queue to traverse nodes level by level

Solution

1. Step 1: Understand the problem requires level-wise traversal

   Collecting nodes level by level means visiting all nodes at depth d before nodes at depth d+1.

2. Step 2: Identify BFS as the natural approach for level order traversal

   BFS uses a queue to process nodes in order of their depth, ensuring correct grouping by levels.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS naturally processes nodes level by level [OK]

Hint: Level order traversal is BFS, not DFS or greedy [OK]

Common Mistakes:

• Confusing DFS with BFS for level order traversal

3. What is the time complexity of the optimal two-stacks zigzag level order traversal algorithm for a binary tree with n nodes?

medium

A. O(n), since each node is visited exactly once and pushed/popped at most twice

B. O(n^2), because pushing children in two stacks doubles the work per node

C. O(n log n), because each level requires reversing the node list

D. O(n), but with O(h) auxiliary space where h is the tree height due to recursion stack

Solution

1. Step 1: Identify node visits

   Each node is pushed and popped exactly once per stack, total constant times per node.

2. Step 2: Analyze operations per node

   Appending children and popping nodes are O(1) operations, no nested loops over nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear traversal with constant work per node -> O(n) time [OK]

Hint: Each node processed once, no repeated work [OK]

Common Mistakes:

• Assuming reversing adds O(n log n)
• Confusing stack pushes as doubling work

4. What is the time complexity of the BFS-based solution for finding the largest value in each tree row, assuming n is the number of nodes and w is the maximum width of the tree?

medium

A. O(n * w) because for each node we scan all nodes at its level

B. O(n log w) due to maintaining a max heap per level

C. O(n) because each node is enqueued and dequeued exactly once

D. O(w) since we only track the maximum per level

Solution

1. Step 1: Identify that each node is processed once

   Each node is enqueued once and dequeued once, so total operations proportional to n.

2. Step 2: Confirm no nested loops over nodes beyond level size

   Inner loop runs for each level's nodes, summing to n overall, so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each node visited once -> O(n) time [OK]

Hint: Each node processed once in BFS -> O(n) time [OK]

Common Mistakes:

• Confusing level width w as multiplicative factor
• Assuming sorting or heap operations per level
• Ignoring that inner loop sums to n over all levels

5. Suppose the problem is extended so that the tree nodes can have multiple children (not just binary), and you need to check if the tree is symmetric around its center. Which modification to the BFS approach is necessary to correctly handle this case?

hard

A. Enqueue children in normal order and compare corresponding children pairs directly

B. Enqueue children in mirrored order and compare pairs from opposite ends of the children list

C. Use a recursive approach only, as BFS cannot handle multiple children

D. Check symmetry only at the root level and ignore deeper levels

Solution

1. Step 1: Understand symmetry in multi-child trees

   Symmetry means the first child on the left subtree mirrors the last child on the right subtree, second mirrors second last, etc.

2. Step 2: Modify BFS to enqueue children in mirrored order

   Enqueue children pairs from opposite ends of the children list to compare mirrored positions correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Mirrored enqueue order for multiple children preserves symmetry checks [OK]

Hint: Multi-child symmetry requires mirrored child pair comparisons [OK]

Common Mistakes:

• Enqueuing children in normal order causing false positives
• Assuming BFS cannot be adapted for multi-child trees
• Ignoring deeper levels of the tree