Explain an iterative inorder invariant

Clarify the observable contract

Traverse an acyclic binary tree in left-node-right order without recursion. The explicit stack stores ancestors whose left descent is in progress and whose node visit remains pending. The structure is assumed to be a tree rather than an arbitrary graph with shared or cyclic links. Sorted output follows only if the input also satisfies a binary-search-tree ordering rule.

The stack is a record of deferred node visits, not a generic visited set. Every time current moves left, the current node is saved because its own value and right subtree remain pending. When no further left node exists, popping selects exactly the next inorder node under the tree assumption.

Walk through the verified program

For the root two, the algorithm pushes two then one. It visits one, returns to two and then descends into the right child three, producing one,two,three. Null input skips the loop entirely. yield return makes traversal lazy: calling Inorder alone does not visit a node, while string.Join and Count enumerate the sequence.

After yielding a node, setting current to its right child starts the same left-descent process for that subtree. A leaf contributes one push, one pop and one yield. The loop condition must allow either a current subtree or pending ancestors, otherwise traversal would stop prematurely when a left descent reaches null.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var root = new Node(2,new Node(1),new Node(3));
Console.WriteLine(string.Join(",",Inorder(root)));
Console.WriteLine("empty:" + Inorder(null).Count());
static IEnumerable<int> Inorder(Node? root) {
    var stack=new Stack<Node>(); Node? current=root;
    while(current is not null || stack.Count>0) {
        while(current is not null) { stack.Push(current); current=current.Left; }
        current=stack.Pop(); yield return current.Value; current=current.Right;
    }
}
sealed record Node(int Value,Node? Left=null,Node? Right=null);

Account for time, storage and allocations

Every node is pushed and popped once, so traversal takes O(n) time and O(h) auxiliary stack space, where h is tree height. A skewed tree makes h equal n. Producing a materialized output array would add O(n) result storage; this iterator itself yields values incrementally.

Lazy output avoids storing the entire traversal result inside the iterator, but a consumer such as ToArray can add that storage afterward. Stack growth follows height, not the number of already yielded nodes. This is why an iterative implementation avoids call-stack recursion limits without guaranteeing constant total memory.

Review assumptions and likely defects

Calling an iterative traversal constant-space merely because it avoids recursion ignores the explicit stack. A cycle can cause an infinite descent, and mutation during lazy enumeration changes what the consumer sees. This sample deliberately relies on an owned immutable node fixture.

A record with immutable child references makes this fixture stable, but arbitrary node graphs can share children or form cycles through another representation. Adding a visited set would change duplicate-visit semantics and space usage. Define whether the task is a tree traversal or a graph traversal before applying such a patch.

Practice one: discriminate edge cases

Build a left-skewed three-node tree and trace the maximum stack size. Hint: record pending ancestors before the first yield. Then use a non-BST tree to show that inorder traversal alone does not guarantee sorted values.

Compare a balanced three-node tree and a three-node chain with the same inorder values. Their output can match while maximum pending depth differs. Keep the output assertion and a separately instrumented depth assertion conceptually distinct; one does not prove the other.

Practice two: defend an extension

Design an API for traversing caller-owned mutable trees. Decide whether to snapshot, reject cycles, lock ownership or document a no-mutation precondition. State the memory and latency consequences before promising safe streaming traversal.

For a mutable caller-owned tree, a copying snapshot offers simple repeatable traversal at O(n) upfront cost. A no-mutation precondition avoids that copy but transfers responsibility to callers. An API should not silently claim both snapshot behavior and allocation-free traversal when it implements neither synchronization nor copying.

Evaluate correctness and interview reasoning

A rigorous explanation states the left-node-right order, describes the pending-ancestor invariant and gives a linear visit-count argument. It qualifies the sorted-output claim with the BST assumption and the space claim with tree height. The sample's empty-tree count checks termination without requiring a fabricated root. When reviewing a lazy API, also identify when enumeration starts and who may mutate the source before or during it. These ownership questions are the practical interview extension beyond the earlier algorithms course's explicit-stack traversal mechanics. A partially consumed traversal should also be disposed by its consumer. The stack holds node references until that enumerator is finished or released, so streaming does not make retained source objects disappear immediately.