DSA-083 · Postorder height certification at every subtree root

Balanced Binary Tree

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 23498 deterministic checks. Learner drafts are not executed.

Understand the problem

Return whether every node’s left and right subtree heights differ by at most one.

Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
Preserve every original value, node identity, and left/right edge. Compact level-order arrays in examples are adapters, consuming two child slots per nonnull queued parent; they are not heap-indexed arrays.
Null is balanced with height 0. The requirement applies at every node, not just the root; values and BST ordering do not affect balance. The method may stop at its first imbalance without completing later frames.

Examples

Input: [3,9,20,null,null,15,7]
Output: true
Every local height difference is zero or one.
Input: [1,2,2,3,null,3,null,4,null,4]
Output: false
Root sides have equal height, but lower nodes each have a two-level imbalance.

Before you start

Tree height and the definition of local balance
Explicit postorder frames and early rejection

Recognize the structure

The parent needs child heights, while the query requires a certificate that every completed subtree is balanced. Postorder can reject a bad local difference immediately and never recompute a successful child height.

Try before revealing

Hint 1

A parent needs more than a boolean from each child.

Hint 2

Compute height and local validity together, once per node.

Hint 3

Use postorder; reject the first completed frame whose child heights differ by more than one.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Check balance using separate height traversals

At each node, recompute both child heights, require a difference at most one, and recursively validate both children. Equal root heights in the second example pass the root test but do not excuse imbalance below it. Repeated scans yield O(nh) worst-case work and recursive depth risk.

Improve the baseline

Use one frame per suspended ancestor

Store stage and two integer child heights. Advance the stage before scheduling its child so the return destination is unambiguous.

Certify a completed node

At stage 2, reject if abs(leftHeight−rightHeight)>1. Otherwise compute 1+max and propagate that certified height.

Stop only on a valid witness

An early false need not finish the remaining right subtrees. Successful stack exhaustion certifies every node; no graph edge is ever written.

Why it is correct

Certified-child invariant

A propagated height belongs to a subtree whose nodes all passed their local balance test. Null children contribute certified height zero.

Local certification or counterexample

Combining two certified subtrees is balanced exactly when their height difference is at most one. A larger difference is itself sufficient to reject the whole tree.

Success and early termination

Each successful combine certifies a larger subtree; completing the root proves the whole tree balanced. Early false is correct even though other frames remain unprocessed.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    private static final class Frame {
        final Node node;
        int stage, leftHeight, rightHeight;
        Frame(Node node) { this.node = node; }
    }
    public static boolean balanced(Node root) {
        if (root == null) return true;
        ArrayDeque<Frame> stack = new ArrayDeque<>();
        stack.push(new Frame(root));
        while (!stack.isEmpty()) {
            Frame frame = stack.peek();
            if (frame.stage == 0) {
                frame.stage = 1;
                if (frame.node.left != null) stack.push(new Frame(frame.node.left));
            } else if (frame.stage == 1) {
                frame.stage = 2;
                if (frame.node.right != null) stack.push(new Frame(frame.node.right));
            } else {
                if (Math.abs(frame.leftHeight-frame.rightHeight) > 1) return false;
                int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
                stack.pop();
                if (!stack.isEmpty()) {
                    Frame parent = stack.peek();
                    if (parent.stage == 1) parent.leftHeight = height;
                    else parent.rightHeight = height;
                }
            }
        }
        return true;
    }
    private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
    public static boolean baseline(Node root) {
        return root == null || Math.abs(height(root.left)-height(root.right)) <= 1 && baseline(root.left) && baseline(root.right);
    }
}

Read the meaningful blocks

Height and balance are different facts

Equal root child heights do not certify the descendants.

Keep early-exit displays honest

A trace that rejects has partial summaries, not heights for every node. Pending frames are abandoned, not silently completed.

Avoid height recomputation

The parent stores a child’s one returned height; no subtree is rescanned.

Complexity

O(n) worst-case time and O(h) explicit frame storage, with earlier termination possible. The implementation writes no per-node height map and returns one boolean.

The baseline has O(nh) worst-case time and O(h) recursive space; some imbalanced trees short-circuit sooner, but that does not improve the worst-case bound.

Exact-state walkthroughs

Reveal normal and boundary traces

Certify child heights bottom up

Input: [3,9,20,null,null,15,7] · Result: true

Step 1 of 17: Create explicit postorder continuations.

Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.

Balance — certified heights and early counterexamples

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 3left → T1right → T2
T1: 9left → nullright → null
T2: 20left → T3right → T4
T3: 15left → nullright → null
T4: 7left → nullright → null

Postorder continuations — stack top at right

T0: stage 0; left 0; right 0

Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.

Only successfully returned heights certify balanced subtrees. On rejection, remaining frames are abandoned.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]`
summaries	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private static final class Frame {
 9         final Node node;
10         int stage, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static boolean balanced(Node root) {
14         if (root == null) return true;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         while (!stack.isEmpty()) {
18             Frame frame = stack.peek();
19             if (frame.stage == 0) {
20                 frame.stage = 1;
21                 if (frame.node.left != null) stack.push(new Frame(frame.node.left));
22             } else if (frame.stage == 1) {
23                 frame.stage = 2;
24                 if (frame.node.right != null) stack.push(new Frame(frame.node.right));
25             } else {
26                 if (Math.abs(frame.leftHeight-frame.rightHeight) > 1) return false;
27                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
28                 stack.pop();
29                 if (!stack.isEmpty()) {
30                     Frame parent = stack.peek();
31                     if (parent.stage == 1) parent.leftHeight = height;
32                     else parent.rightHeight = height;
33                 }
34             }
35         }
36         return true;
37     }
38     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
39     public static boolean baseline(Node root) {
40         return root == null || Math.abs(height(root.left)-height(root.right)) <= 1 && baseline(root.left) && baseline(root.right);
41     }
42 }
43

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"initial"
current
null
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-left"
current
"T0"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-left"
current
"T1"
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-right"
current
"T1"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"combine"
current
"T1"
last
{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-right"
current
"T0"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-left"
current
"T2"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-left"
current
"T3"
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-right"
current
"T3"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"combine"
current
"T3"
last
{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T4","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-right"
current
"T2"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T4","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-left"
current
"T4"
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T4","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-right"
current
"T4"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T2","stage":2,"leftHeight":1,"rightHeight":1}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"combine"
current
"T4"
last
{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":1,"rightHeight":2}]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T2","leftHeight":1,"rightHeight":1,"height":2,"balanced":true}]
phase
"combine"
current
"T2"
last
{"id":"T2","leftHeight":1,"rightHeight":1,"height":2,"balanced":true}
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
stack
[]
summaries
[{"id":"T1","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T2","leftHeight":1,"rightHeight":1,"height":2,"balanced":true},{"id":"T0","leftHeight":1,"rightHeight":2,"height":3,"balanced":true}]
phase
"combine"
current
"T0"
last
{"id":"T0","leftHeight":1,"rightHeight":2,"height":3,"balanced":true}
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
true

Root balance does not certify descendants

Input: [1,2,2,3,null,3,null,4,null,4] · Result: false

Step 1 of 12: Create explicit postorder continuations.

Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.

Balance — certified heights and early counterexamples

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 1left → T1right → T2
T1: 2left → T3right → null
T2: 2left → T4right → null
T3: 3left → T5right → null
T4: 3left → T6right → null
T5: 4left → nullright → null
T6: 4left → nullright → null

Postorder continuations — stack top at right

T0: stage 0; left 0; right 0

Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.

Only successfully returned heights certify balanced subtrees. On rejection, remaining frames are abandoned.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]`
summaries	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private static final class Frame {
 9         final Node node;
10         int stage, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static boolean balanced(Node root) {
14         if (root == null) return true;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         while (!stack.isEmpty()) {
18             Frame frame = stack.peek();
19             if (frame.stage == 0) {
20                 frame.stage = 1;
21                 if (frame.node.left != null) stack.push(new Frame(frame.node.left));
22             } else if (frame.stage == 1) {
23                 frame.stage = 2;
24                 if (frame.node.right != null) stack.push(new Frame(frame.node.right));
25             } else {
26                 if (Math.abs(frame.leftHeight-frame.rightHeight) > 1) return false;
27                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
28                 stack.pop();
29                 if (!stack.isEmpty()) {
30                     Frame parent = stack.peek();
31                     if (parent.stage == 1) parent.leftHeight = height;
32                     else parent.rightHeight = height;
33                 }
34             }
35         }
36         return true;
37     }
38     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
39     public static boolean baseline(Node root) {
40         return root == null || Math.abs(height(root.left)-height(root.right)) <= 1 && baseline(root.left) && baseline(root.right);
41     }
42 }
43

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"initial"
current
null
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-left"
current
"T0"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-left"
current
"T1"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T5","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-left"
current
"T3"
Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T5","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-left"
current
"T5"
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T5","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[]
phase
"enter-right"
current
"T5"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"combine"
current
"T5"
last
{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"balanced":true}]
phase
"enter-right"
current
"T3"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":2,"rightHeight":0}]
summaries
[{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":1,"rightHeight":0,"height":2,"balanced":true}]
phase
"combine"
current
"T3"
last
{"id":"T3","leftHeight":1,"rightHeight":0,"height":2,"balanced":true}
Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0}]
summaries
[{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":1,"rightHeight":0,"height":2,"balanced":true}]
phase
"enter-right"
current
"T1"
Reject this completed node’s height gap.
Previously returned heights are certified balanced; this local gap disproves the whole tree. Pending frames are abandoned, not completed.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":null},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":"T5","right":null},{"id":"T4","value":3,"left":"T6","right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":4,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0}]
summaries
[{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"balanced":true},{"id":"T3","leftHeight":1,"rightHeight":0,"height":2,"balanced":true}]
phase
"reject"
current
"T1"
last
{"id":"T1","leftHeight":2,"rightHeight":0,"balanced":false}
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
false

Empty tree is balanced

Input: [] · Result: true

Step 1 of 2: Create explicit postorder continuations.

Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.

Balance — certified heights and early counterexamples

Phase: initial. Current identity: null.

Original objects — unchanged source edges

Empty tree.

Postorder continuations — stack top at right

Empty.

Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.

Only successfully returned heights certify balanced subtrees. On rejection, remaining frames are abandoned.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
stack	`[]`
summaries	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private static final class Frame {
 9         final Node node;
10         int stage, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static boolean balanced(Node root) {
14         if (root == null) return true;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         while (!stack.isEmpty()) {
18             Frame frame = stack.peek();
19             if (frame.stage == 0) {
20                 frame.stage = 1;
21                 if (frame.node.left != null) stack.push(new Frame(frame.node.left));
22             } else if (frame.stage == 1) {
23                 frame.stage = 2;
24                 if (frame.node.right != null) stack.push(new Frame(frame.node.right));
25             } else {
26                 if (Math.abs(frame.leftHeight-frame.rightHeight) > 1) return false;
27                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
28                 stack.pop();
29                 if (!stack.isEmpty()) {
30                     Frame parent = stack.peek();
31                     if (parent.stage == 1) parent.leftHeight = height;
32                     else parent.rightHeight = height;
33                 }
34             }
35         }
36         return true;
37     }
38     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
39     public static boolean baseline(Node root) {
40         return root == null || Math.abs(height(root.left)-height(root.right)) <= 1 && baseline(root.left) && baseline(root.right);
41     }
42 }
43

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
treeNodes
[]
root
null
stack
[]
summaries
[]
phase
"initial"
current
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
true

Test the contract

Input: null
Output: true
Empty subtree is certified.
Input: Single leaf
Output: true
Both child heights zero.
Input: Equal root heights with an internal gap of two
Output: false
All-node property.
Input: 100,000-node chain
Output: false
Early witness without recursive overflow.

Common mistakes and counterexamples

Check only the root’s height difference

Counterexample: Equal-height sides may both contain unbalanced descendants.

Require every subtree’s certification.

Compare node counts instead of heights

Counterexample: A shallow wide subtree can have more nodes than a narrow deep one.

Return longest-path heights, not sizes.

Declare all frames certified after early false

Counterexample: Some siblings were never visited.

Mark only completed summaries and preserve the rejecting witness.

Follow-ups

Return the first unbalanced identity.

Return the stage-2 node that fails and define traversal order. An optional identity is clearer than inventing a sentinel value.

Generalize the tolerated height gap.

Replace one by an explicit nonnegative threshold. The same certification proof holds; this is still a shape property, not an AVL insertion algorithm.

Balance after updates.

A static O(n) check does not maintain balance under insertion. AVL or red-black trees require stored metadata, rotations and stronger update invariants.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 161/20,000 characters

Self-review

Can I name what a returned height certifies?Can I produce a counterexample to checking only the root?Can I explain which summaries exist after early rejection?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.