Balanced Binary Tree

🎯

Balanced Binary Tree

easyTREEAmazonGoogleBloomberg

Imagine you are designing a system that needs to keep data balanced for efficient retrieval, like a balanced family tree where no branch is too deep compared to others.

💡 This problem asks if a binary tree is height-balanced, meaning the depths of left and right subtrees of every node differ by no more than one. Beginners often struggle because they try to check balance and height separately, leading to inefficient solutions.

📋

Problem Statement

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Input: The root node of a binary tree. Output: Return true if the tree is height-balanced, otherwise false.

1 ≤ n ≤ 10^5 (number of nodes)Node values can be any integerTree can be skewed or complete

💡

Example

Input"root = [3,9,20,null,null,15,7]"

Outputtrue

The left subtree height is 1, right subtree height is 2, difference is 1 which is allowed.

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

Outputfalse

The left subtree is deeper by more than 1 level, so the tree is not balanced.

• Empty tree → true (an empty tree is balanced)
• Single node tree → true (only one node, balanced)
• Completely skewed tree (all nodes only on one side) → false
• Tree with subtrees differing in height by exactly 1 → true

⚠️

Common Mistakes

Computing height separately for each node without caching

Leads to O(n^2) time and TLE on large inputs

✅ Combine height and balance check in one recursion with early exit

Not handling empty tree as balanced

Incorrectly returns false or errors on null root

✅ Return true if root is null

Checking balance only at root node

Misses imbalance in subtrees, returns incorrect true

✅ Check balance condition at every node recursively

Using global variables for height without resetting

Incorrect results due to stale values

✅ Use return values or pass parameters instead of globals

Not using absolute difference when comparing heights

Incorrect balance checks, false negatives or positives

✅ Use abs(left_height - right_height) to compare

🧠

Brute Force (Separate Height and Balance Checks)

💡 This approach exists to build intuition by directly translating the problem definition into code, even though it is inefficient. It helps beginners understand the problem deeply before optimizing.

Intuition

Check if the tree is balanced by recursively checking the height difference at each node, computing subtree heights independently for each node.

Algorithm

1. Define a function to compute the height of a subtree.
2. Define a function to check if a subtree is balanced by comparing heights of left and right subtrees.
3. Recursively check balance for every node in the tree.
4. Return true if all nodes satisfy the height difference condition.

💡 The challenge is that height is recomputed multiple times for the same nodes, causing inefficiency.

</>

Code

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

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

def isBalanced(root):
    if not root:
        return True
    left_height = height(root.left)
    right_height = height(root.right)
    if abs(left_height - right_height) > 1:
        return False
    return isBalanced(root.left) and isBalanced(root.right)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(isBalanced(root))  # Expected: True

Line Notes

def height(root):Defines a helper to compute subtree height from current node to measure depth

if not root:Base case: empty subtree has height 0, which stops recursion

return 1 + max(height(root.left), height(root.right))Height is 1 plus the maximum height of left and right children, representing current node's height

if abs(left_height - right_height) > 1:Check if current node violates balance condition by comparing subtree heights

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

public class Solution {
    public int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (Math.abs(leftHeight - rightHeight) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.isBalanced(root)); // true
    }
}

Line Notes

public int height(TreeNode root) {Helper method to compute height of subtree rooted at given node

if (root == null) return 0;Base case for empty subtree returns height zero

if (Math.abs(leftHeight - rightHeight) > 1) return false;Check if current node violates balance condition

return isBalanced(root.left) && isBalanced(root.right);Recursively check balance condition for left and right subtrees

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

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

int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

bool isBalanced(TreeNode* root) {
    if (!root) return true;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(root->left) && isBalanced(root->right);
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << (isBalanced(root) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

int height(TreeNode* root) {Computes height of subtree rooted at given node

if (!root) return 0;Base case: empty subtree has height zero

if (abs(leftHeight - rightHeight) > 1) return false;Check if current node is balanced by comparing subtree heights

return isBalanced(root->left) && isBalanced(root->right);Recursively verify balance for left and right subtrees

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function height(root) {
    if (!root) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

function isBalanced(root) {
    if (!root) return true;
    const leftHeight = height(root.left);
    const rightHeight = height(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(isBalanced(root)); // true

Line Notes

function height(root) {Helper function to compute height of subtree from current node

if (!root) return 0;Base case: empty subtree has height zero

if (Math.abs(leftHeight - rightHeight) > 1) return false;Check if current node violates balance condition

return isBalanced(root.left) && isBalanced(root.right);Recursively check balance for left and right subtrees

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each node, height is computed recursively which takes O(n) in worst case, repeated for all nodes leads to O(n^2).

💡 For n=20 nodes, this means roughly 400 operations, which grows quickly and becomes inefficient for large trees.

Interview Verdict: TLE for large inputs

This approach is too slow for large trees but is useful to understand the problem and correctness before optimizing.

🧠

Optimized Recursion with Early Exit (Postorder Traversal)

💡 This approach improves efficiency by combining height calculation and balance check in one recursion, avoiding repeated height computations.

Intuition

Use a postorder traversal to compute height bottom-up, returning -1 immediately if an unbalanced subtree is found to stop further unnecessary checks.

Algorithm

1. Define a recursive function that returns the height of a subtree or -1 if unbalanced.
2. Recursively compute left and right subtree heights.
3. If either subtree is unbalanced, propagate -1 upwards immediately.
4. If height difference exceeds 1, return -1 to indicate imbalance.
5. Otherwise, return the height of the current subtree.
6. Check if the final result is -1 to determine if the tree is balanced.

💡 The key insight is to propagate failure (-1) early to avoid redundant computations.

</>

Code

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

def check_height(root):
    if not root:
        return 0
    left_height = check_height(root.left)
    if left_height == -1:
        return -1
    right_height = check_height(root.right)
    if right_height == -1:
        return -1
    if abs(left_height - right_height) > 1:
        return -1
    return 1 + max(left_height, right_height)

def isBalanced(root):
    return check_height(root) != -1

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(isBalanced(root))  # Expected: True

Line Notes

def check_height(root):Helper returns height or -1 if unbalanced to combine checks

if left_height == -1:Early exit if left subtree is unbalanced to avoid extra work

if abs(left_height - right_height) > 1:Detect imbalance at current node by height difference

return 1 + max(left_height, right_height)Return height if subtree is balanced

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

public class Solution {
    public int checkHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return 1 + Math.max(leftHeight, rightHeight);
    }

    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.isBalanced(root)); // true
    }
}

Line Notes

public int checkHeight(TreeNode root) {Returns height or -1 if subtree is unbalanced to combine logic

if (leftHeight == -1) return -1;Stop early if left subtree is unbalanced to save computation

if (Math.abs(leftHeight - rightHeight) > 1) return -1;Detect imbalance at current node by height difference

return 1 + Math.max(leftHeight, rightHeight);Return height if subtree is balanced

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

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

int checkHeight(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) return -1;
    int rightHeight = checkHeight(root->right);
    if (rightHeight == -1) return -1;
    if (abs(leftHeight - rightHeight) > 1) return -1;
    return 1 + max(leftHeight, rightHeight);
}

bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << (isBalanced(root) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

int checkHeight(TreeNode* root) {Returns height or -1 if subtree is unbalanced to combine height and balance check

if (leftHeight == -1) return -1;Early return if left subtree is unbalanced to avoid further checks

if (abs(leftHeight - rightHeight) > 1) return -1;Check balance condition at current node

return 1 + max(leftHeight, rightHeight);Return height if balanced

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function checkHeight(root) {
    if (!root) return 0;
    const leftHeight = checkHeight(root.left);
    if (leftHeight === -1) return -1;
    const rightHeight = checkHeight(root.right);
    if (rightHeight === -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    return 1 + Math.max(leftHeight, rightHeight);
}

function isBalanced(root) {
    return checkHeight(root) !== -1;
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(isBalanced(root)); // true

Line Notes

function checkHeight(root) {Returns height or -1 if subtree is unbalanced to combine checks efficiently

if (leftHeight === -1) return -1;Stop recursion early if left subtree is unbalanced

if (Math.abs(leftHeight - rightHeight) > 1) return -1;Detect imbalance at current node by height difference

return 1 + Math.max(leftHeight, rightHeight);Return height if balanced

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, and height is computed in the same recursion, so O(n) time. Space is O(h) due to recursion stack where h is tree height.

💡 For n=20 nodes, this means about 20 operations, much faster than brute force.

Interview Verdict: Accepted

This is the standard efficient solution expected in interviews.

🧠

Iterative Postorder Traversal with Stack

💡 This approach uses an explicit stack to simulate postorder traversal iteratively, useful if recursion is limited or to demonstrate mastery of tree traversal techniques.

Intuition

Use a stack to traverse the tree postorder, computing heights bottom-up and storing them in a map, checking balance as we go.

Algorithm

1. Use a stack to traverse nodes in postorder iteratively.
2. Maintain a map/dictionary to store heights of visited nodes.
3. For each node, after visiting children, compute height and check balance.
4. If imbalance detected, return false immediately.
5. If traversal completes without imbalance, return true.

💡 This approach is more complex but avoids recursion stack limits and shows control over traversal order.

</>

Code

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

def isBalanced(root):
    if not root:
        return True
    stack = []
    node = root
    last_visited = None
    heights = {}
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_height = heights.get(peek.left, 0)
                right_height = heights.get(peek.right, 0)
                if abs(left_height - right_height) > 1:
                    return False
                heights[peek] = 1 + max(left_height, right_height)
                last_visited = stack.pop()
    return True

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(isBalanced(root))  # Expected: True

Line Notes

stack = []Stack to simulate recursion for iterative traversal

while stack or node:Continue until all nodes are processed

if node: stack.append(node)Traverse left subtree as far as possible

if abs(left_height - right_height) > 1:Check balance condition at current node using stored heights

import java.util.*;

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

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> stack = new ArrayDeque<>();
        Map<TreeNode, Integer> heights = new HashMap<>();
        TreeNode node = root, lastVisited = null;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right != null && lastVisited != peek.right) {
                    node = peek.right;
                } else {
                    int leftHeight = heights.getOrDefault(peek.left, 0);
                    int rightHeight = heights.getOrDefault(peek.right, 0);
                    if (Math.abs(leftHeight - rightHeight) > 1) return false;
                    heights.put(peek, 1 + Math.max(leftHeight, rightHeight));
                    lastVisited = stack.pop();
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.isBalanced(root)); // true
    }
}

Line Notes

Deque<TreeNode> stack = new ArrayDeque<>();Stack to simulate recursion for iterative traversal

while (!stack.isEmpty() || node != null) {Traverse until all nodes are processed

if (peek.right != null && lastVisited != peek.right) {Traverse right subtree if not yet visited

if (Math.abs(leftHeight - rightHeight) > 1) return false;Check balance condition at current node

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

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

bool isBalanced(TreeNode* root) {
    if (!root) return true;
    stack<TreeNode*> stk;
    unordered_map<TreeNode*, int> heights;
    TreeNode* node = root;
    TreeNode* lastVisited = nullptr;
    while (!stk.empty() || node) {
        if (node) {
            stk.push(node);
            node = node->left;
        } else {
            TreeNode* peek = stk.top();
            if (peek->right && lastVisited != peek->right) {
                node = peek->right;
            } else {
                int leftHeight = heights.count(peek->left) ? heights[peek->left] : 0;
                int rightHeight = heights.count(peek->right) ? heights[peek->right] : 0;
                if (abs(leftHeight - rightHeight) > 1) return false;
                heights[peek] = 1 + max(leftHeight, rightHeight);
                lastVisited = peek;
                stk.pop();
            }
        }
    }
    return true;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << (isBalanced(root) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

stack<TreeNode*> stk;Stack to simulate recursion for iterative traversal

while (!stk.empty() || node) {Traverse until all nodes are processed

if (peek->right && lastVisited != peek->right) {Traverse right subtree if not yet visited

if (abs(leftHeight - rightHeight) > 1) return false;Check balance condition at current node

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isBalanced(root) {
    if (!root) return true;
    const stack = [];
    const heights = new Map();
    let node = root;
    let lastVisited = null;
    while (stack.length > 0 || node !== null) {
        if (node !== null) {
            stack.push(node);
            node = node.left;
        } else {
            const peek = stack[stack.length - 1];
            if (peek.right !== null && lastVisited !== peek.right) {
                node = peek.right;
            } else {
                const leftHeight = heights.get(peek.left) || 0;
                const rightHeight = heights.get(peek.right) || 0;
                if (Math.abs(leftHeight - rightHeight) > 1) return false;
                heights.set(peek, 1 + Math.max(leftHeight, rightHeight));
                lastVisited = stack.pop();
            }
        }
    }
    return true;
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(isBalanced(root)); // true

Line Notes

const stack = [];Stack to simulate recursion for iterative traversal

while (stack.length > 0 || node !== null) {Traverse until all nodes are processed

if (peek.right !== null && lastVisited !== peek.right) {Traverse right subtree if not yet visited

if (Math.abs(leftHeight - rightHeight) > 1) return false;Check balance condition at current node

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, and heights stored in a map. Stack space is O(h) where h is tree height.

💡 For n=20 nodes, this is efficient and avoids recursion stack overflow.

Interview Verdict: Accepted

This approach is less common but useful when recursion is restricted or to demonstrate iterative traversal skills.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 is the best to implement in interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	Yes (deep recursion)	N/A	Mention only - never code
2. Optimized Recursion with Early Exit	O(n)	O(h)	Yes (depends on tree height)	N/A	Code this approach
3. Iterative Postorder Traversal	O(n)	O(h)	No	N/A	Mention if recursion is restricted

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and confirm the definition of balanced tree.State the brute force approach and its inefficiency.Explain the optimized recursive approach with early exit.Optionally mention iterative approach if recursion is a concern.Write clean code and test with examples.

Time Allocation

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

What the Interviewer Tests

Understanding of tree traversal, recursion, optimization to avoid repeated work, and ability to handle edge cases.

Common Follow-ups

• What if the tree is very deep? → Use iterative approach or tail recursion optimization.
• Can you return the height of the tree if balanced? → Yes, the optimized function returns height or -1.

💡 These follow-ups test deeper understanding of recursion limits and ability to extend the solution.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree property check 2) Requires subtree height or depth info 3) Needs to verify condition at every node 4) Balance or height difference constraints

Signature Phrases

height-balanceddifference in heightleft and right subtrees

NOT This Pattern When

Problems that only require traversal without subtree property checks, e.g., inorder traversal printing.

Similar Problems

Check Completeness of a Binary Tree - also involves tree property validationMaximum Depth of Binary Tree - focuses on height calculationDiameter of Binary Tree - uses postorder traversal to compute subtree info

Practice

1. You are given a binary tree where each node contains a non-negative integer value. You want to maximize the sum of values you can collect by selecting nodes such that no two directly connected nodes (parent-child) are both selected. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that always picks the node with the highest value first.

B. Use a depth-first search with dynamic programming that returns two values per node: max if robbing it and max if not robbing it.

C. Use a breadth-first search to select nodes level by level, picking the maximum values at alternate levels.

D. Use a brute force recursion that tries all subsets of nodes without any memoization.

Solution

1. Step 1: Understand the problem constraints

   The problem requires selecting nodes in a tree such that no parent and child are both selected, maximizing the sum of selected nodes.

2. Step 2: Identify the suitable algorithmic pattern

   A greedy or BFS level-based approach fails because the tree structure and adjacency constraints are complex. Brute force is correct but inefficient. The optimal solution uses DFS with DP returning two values per node: max if robbing it and max if not robbing it, ensuring all subproblems are solved optimally.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS with two-value DP handles adjacency constraints correctly [OK]

Hint: Tree + no adjacent nodes -> DFS with two-value DP [OK]

Common Mistakes:

• Assuming greedy or level-based selection works
• Trying brute force without memoization

2. What is the time complexity of the optimized recursive solution that uses a hash map for index lookup when constructing a binary tree from inorder and postorder traversals of size n?

medium

A. O(n) because each node is processed once and index lookup is O(1)

B. O(n^2) due to repeated slicing of arrays

C. O(n log n) because of balanced tree recursion depth

D. O(n) but with O(n) auxiliary space for recursion stack and hash map

Solution

1. Step 1: Analyze time complexity

   Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.

2. Step 2: Analyze space complexity

   Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is O(n), space includes recursion stack and hash map [OK]

Hint: Hash map reduces search to O(1), recursion stack adds O(n) space [OK]

Common Mistakes:

• Assuming slicing causes O(n^2) time
• Ignoring recursion stack space
• Confusing balanced tree depth with complexity

3. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?

medium

A. Line creating root node with postorder[-1]

B. Line initializing inorder_index to 0

C. Line attaching node as right child

D. Line popping from stack inside while loop

Solution

1. Step 1: Identify inorder_index initialization

   inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.

2. Step 2: Consequences of wrong initialization

   Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct inorder_index initialization is critical for stack popping logic [OK]

Hint: inorder_index must start at last index, not zero [OK]

Common Mistakes:

• Wrong inorder_index initialization
• Confusing postorder traversal direction
• Incorrect stack popping conditions

4. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?

medium

A. O(n^2) due to checking grandchildren nodes explicitly

B. O(n) but with extra O(n) space for memoization arrays

C. O(n) because each node is visited once in DFS

D. O(n log n) because of recursive calls and combining results

Solution

1. Step 1: Identify DFS traversal cost

   The algorithm visits each node exactly once in a postorder DFS traversal.

2. Step 2: Analyze operations per node

   At each node, constant time operations are done: combining left and right child results, no repeated work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal of n nodes -> O(n) time [OK]

Hint: DFS visits each node once, no repeated subproblems [OK]

Common Mistakes:

• Assuming O(n^2) due to grandchildren checks
• Confusing recursion stack space with time complexity

5. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:

medium

A. O(n), but with O(n) auxiliary space for the queue at the widest level

B. O(n), because each node is visited exactly once in BFS

C. O(n log n), because each level requires sorting nodes

D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

1. Step 1: Identify time complexity

   BFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity and common misconception

   Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node enqueued and dequeued once; max queue size O(n) [OK]

Hint: BFS visits each node once; space depends on max level width [OK]

Common Mistakes:

• Assuming multiple visits per node
• Confusing sorting with traversal
• Ignoring queue space usage