Trees & Backtracking

Part 7. Three tree variations — a height check that returns a sentinel, a BFS that grabs the last node per level, and a DFS that carries state down — then the backtracking template extended to handle duplicates.

Tree node, as before:

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

1. Balanced Binary Tree

Is every node's two subtrees' heights within 1 of each other?

Compute height and check balance in one pass by overloading the return value: return the real height if balanced, or a sentinel −1 to signal "already unbalanced" that propagates straight up.

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

private int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);
    if (left == -1) return -1;                       // short-circuit: subtree already unbalanced
    int right = height(node.right);
    if (right == -1) return -1;
    if (Math.abs(left - right) > 1) return -1;        // this node is unbalanced
    return 1 + Math.max(left, right);                 // balanced → real height
}

The −1 sentinel folds "is it balanced?" into the height computation, avoiding a separate O(n)-per-node height call (which would make it O(n²)).

Time: O(n). Space: O(h).

Prep note. Encoding a boolean failure into a numeric return (here −1) is a clean way to compute-and-validate in a single traversal. The naive "call height at every node" is the O(n²) trap to avoid.

2. Binary Tree Right Side View

Return the values visible from the right — the last node at each level.

BFS level by level; the last node dequeued in each level is the one seen from the right. It's the level-order template with a one-line tweak.

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == size - 1) res.add(node.val);     // last node on this level = rightmost
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return res;
}

Taking the node at i == size − 1 picks the rightmost per level; enqueue left-then-right so that node really is the far right.

Time: O(n). Space: O(n).

Prep note. Left Side View is the mirror (take i == 0). Any "per-level extremity" question is the level-order skeleton plus a selection condition.

3. Count Good Nodes

A node is "good" if no node on the path from the root to it has a greater value. Count them.

Carry the running maximum along the path down the recursion. A node is good when its value is at least that max; then pass the updated max to its children. State flows downward here (unlike the upward returns above).

public int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
}

private int dfs(TreeNode node, int maxSoFar) {
    if (node == null) return 0;
    int good = node.val >= maxSoFar ? 1 : 0;          // no larger ancestor on the path
    int newMax = Math.max(maxSoFar, node.val);
    return good + dfs(node.left, newMax) + dfs(node.right, newMax);
}

Threading maxSoFar as a parameter is the "state flows down" pattern — the complement to "answers bubble up."

Time: O(n). Space: O(h).

Prep note. Note the direction: some tree problems push context down (path max, depth, valid range), others pull answers up (height, sums). Knowing which a problem needs is half the battle.

4. Subsets II

Return all subsets of an array that may contain duplicates, without duplicate subsets.

The Blind-75 Subsets template plus a de-dup rule: sort first, then within a recursion level, skip an element equal to the previous one (i > start && nums[i] == nums[i-1]) — that prevents generating the same subset twice.

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);                                 // bring duplicates adjacent
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;   // skip duplicate at this level
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

The i > start guard is precise: it skips duplicates across sibling branches but still lets a duplicate be used deeper in the same path.

Time: O(n · 2ⁿ). Space: O(n) depth.

Prep note. This exact sort-then-skip-equal-siblings rule de-duplicates Combination Sum II and Permutations II as well. It's the standard fix whenever the input has repeats.

The pattern, in one line

Trees push state down (running max, valid range) or pull answers up (height, spans) — pick the direction the problem needs, and use a sentinel return to compute-and-validate in one pass. Backtracking over inputs with repeats is the usual template plus sort + skip-equal-siblings.

Next in Part 8: Backtracking — combinations with duplicates, permutations, phone letters, and partitioning.