🧠 Amazon Interview Experience — Binary Trees, Backtracking, and Greedy Algorithms

✅ Round 1: Online Coding Assessment

🔹 Problem 1: Maximum Average of Subtree

Approach:

Perform a post-order traversal. At each node, calculate:

• The sum of the subtree
• The number of nodes in the subtree
• The average, and update the global max average.

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

function maximumAverageSubtree(root) {
  let maxAvg = -Infinity;

  function dfs(node) {
    if (!node) return { sum: 0, count: 0 };

    const left = dfs(node.left);
    const right = dfs(node.right);

    const sum = node.val + left.sum + right.sum;
    const count = 1 + left.count + right.count;
    const avg = sum / count;

    maxAvg = Math.max(maxAvg, avg);
    return { sum, count };
  }

  dfs(root);
  return maxAvg;
}

🔹 Problem 2: Backtracking on Array (Unremembered)

Let’s assume a classic backtracking problem: Subset Sum

function subsetSum(arr, target) {
  const result = [];

  function backtrack(start, path, sum) {
    if (sum === target) {
      result.push([...path]);
      return;
    }

    if (sum > target) return;

    for (let i = start; i < arr.length; i++) {…