Coding interviews
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);
Reveal answer and reasoning
The output lines, in order, are “1,2,3”; “empty:0”. 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.
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. 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.
What a strong answer covers
- Exact output: 1,2,3 | empty:0
- For the root two, the algorithm pushes two then one.
- Calling an iterative traversal constant-space merely because it avoids recursion ignores the explicit stack.
Common pitfall
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.
Follow-up questions
- 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.
- Would the same traversal be correct for a DAG with a shared child, and what would a visited set change?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.