Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Preorder visits node, then left, then right; inorder visits left, then node, then right; postorder visits left, then right, then node; all three are depth-first traversals (DFS), following one branch as deep as possible before backtracking. Level-order (breadth-first search, BFS) instead visits every node one full depth at a time using a queue. To reconstruct a tree from a serialized form, preorder combined with explicit null markers is the natural single-pass choice, because each value tells you exactly where to place it in the recursion without needing a second array to cross-reference.

Structured elaboration

Recursive versus iterative cost. A recursive traversal uses the call stack, which costs $O(h)$ space where h is the tree's height ($O(\log n)$ for a balanced tree, $O(n)$ worst case for a completely skewed one). An iterative version with an explicit stack (for the depth-first orders) or queue (for level order) has the same asymptotic space cost, but it avoids the recursion-depth limits some language runtimes impose, which matters for very deep, skewed trees.

Level order grouped by depth. Enqueue the root, then repeatedly record the queue's current size before draining exactly that many nodes: that snapshot is what lets you know where one depth level ends and the next begins, since each drained node's children get enqueued for the following level.

Choosing preorder-with-nulls for reconstruction. Preorder plus null sentinels needs only one traversal: read a value, recursively build its left child from what follows, then its right child, treating a null marker as "no subtree here." Preorder plus inorder (without nulls) also works, but only if all values are unique, and it needs an auxiliary index map over the inorder sequence to avoid an $O(n^2)$ naive search, adding bookkeeping the null-marker approach does not need. Level order with null markers is workable too (BFS serialization), but reconstructing parent-child links across levels needs more bookkeeping than the purely recursive preorder approach.

Related extensions from the same traversal family. A BST iterator (an object that exposes a paused, resumable inorder walk) keeps the explicit stack alive across calls instead of finishing the traversal eagerly, giving amortized (averaged over a sequence of operations) $O(1)$ time per next() call. Finding all node pairs at distance k from a target reuses the same level-by-level machinery as level-order traversal, just starting the breadth-first search from the target node instead of the root. The height-balance check, maximum path sum, and invert-binary-tree problems are all further applications of the postorder shape: each recursive call computes something (a height, a best path so far, a swapped subtree) from its children and returns it up to its parent, rather than printing a value as it visits.

graph TD
  A[3] --> B[9]
  A --> C[20]
  C --> D[15]
  C --> E[7]

Worked example

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_vals = []
        for _ in range(len(queue)):  # freeze this level's size before draining
            node = queue.popleft()
            level_vals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_vals)
    return result


if __name__ == "__main__":
    root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(level_order(root))

Running this on the tree pictured above prints [[3], [9, 20], [15, 7]].

Complexity

Time: $O(n)$ for all four traversals (preorder, inorder, postorder, and level-order), since each one visits every node exactly once and does $O(1)$ work per visit.
Space: $O(h)$ for the three depth-first traversals, from the recursion call stack (or an explicit stack for an iterative version), where h is the tree's height, as already noted above. The level-order queue never holds more nodes than one full level of the tree, which is at most $O(n)$ in the worst case (a wide, shallow tree).

Edge cases

• Empty tree (root is None): level_order already returns [] via its explicit check; the depth-first traversals equally return immediately for a None node.
• Single-node tree: all four traversals visit just that one node and produce a single-element result.
• A skewed (essentially linear) tree: recursive depth-first traversals can hit a language's default recursion-depth limit (for example, Python's default is around 1000 frames), which is a concrete argument for the iterative forms in production code.

Trade-offs & pitfalls

The most common bug in the level-order implementation is not snapshotting len(queue) before the inner loop starts; without that snapshot, nodes from the next level get enqueued and then immediately drained in the same pass, smearing two levels together.

Direct answer

A plain stack already gives $O(1)$ push, pop, and top because those operations only ever touch the top element. The trick for $O(1)$ minimum retrieval is to keep a second, parallel stack that tracks what the minimum would be after each push: whenever you push a value onto the main stack, you also push the smaller of that value and the previous minimum onto the min-stack, so its top is always the correct current minimum, and popping both stacks together keeps them in sync without ever rescanning.

Approach

• Maintain two stacks of equal length at all times: stack holds the real values, min_stack holds, at each position, what the minimum was after that push.
• push(x): append x to stack. Append x to min_stack if min_stack is empty or x is less than or equal to its current top; otherwise append the current top again (repeating the still-current minimum).
• pop(): pop from both stacks together; the value from stack is returned, the value from min_stack is discarded.
• get_min(): return min_stack's top directly.

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]


if __name__ == "__main__":
    s = MinStack()
    s.push(5)
    s.push(3)
    s.push(7)
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 5
    print(s.top())       # 5

Running this prints 3, 3, 5, 5: after pushing 5, 3, 7 the minimum is 3; popping 7 (the top) leaves the minimum still 3; popping 3 next leaves only 5, so both the minimum and the top become 5.

Key points

• Using <= (not strict <) when deciding whether to push a new minimum is what makes duplicate minimum values work correctly: if two entries tie for the minimum and you only recorded the first, popping it would incorrectly raise the recorded minimum before the still-present duplicate is gone.
• An alternative "encoded delta" trick stores a single stack, keeping only a running minimum variable, and pushes a value relative to that minimum instead of the raw value, updating the running minimum on push/pop as needed. It roughly halves auxiliary storage but is more error-prone to implement correctly, especially in fixed-width-integer languages (C++, Java) where the encoded delta itself can overflow if the gap between the pushed value and the previous minimum is large.

Complexity

Time: $O(1)$ for every operation (push, pop, top, get_min). Space: $O(n)$ auxiliary for $n$ elements (two stacks, each up to size $n$; a larger constant factor than a single stack, but still linear).

Edge cases

• pop or top on an empty stack should raise or otherwise signal an error rather than reading past the end.
• Duplicate values at the current minimum: handled correctly only if the min-stack push condition uses <=, not <.
• A single-element stack: get_min() must equal top().

Direct answer

Size each field to the minimum number of bits its actual value range needs, then pack them into one machine word using explicit shifts and masks: here, a 6-bit sensor ID, 4 boolean flags, a 10-bit unsigned humidity, and a 12-bit signed temperature add up to exactly $6 + 4 + 10 + 12 = 32\ \text{bits} = 4\ \text{bytes}$, one 32-bit word. Giving each field its own natural type instead (int16_t temperature, uint16_t humidity, uint8_t flags, uint8_t sensor_id, since the 10-bit and 12-bit ranges don't fit in a byte) costs $2 + 2 + 1 + 1 = 6\ \text{bytes}$, so packing saves roughly a third of the memory per record, at the cost of a shift, a mask, and (for the signed field) a sign-extension on every access, plus explicit handling of endianness and alignment that a per-field layout would otherwise get almost for free from the compiler.

Structured elaboration

Approach

• Budget bits from value ranges, not from convenient type widths: sensor_id 0..63 needs 6 bits; 4 independent boolean flags need 4 bits; humidity 0..1023 (tenths of a percent) needs 10 bits; temperature -2048..2047 (tenths of a degree, two's complement) needs 12 bits.
• Fix a layout, most significant bit (MSB) to least significant bit (LSB): [ sensor_id(6) | flags(4) | humidity(10) | temperature(12) ], packed into a uint32_t.
• Use explicit shifts and masks, not C bitfields (struct { unsigned id:6; ... };). The C standard leaves bitfield bit order, padding, and even the underlying storage's byte order implementation-defined, so two compilers, or two build configurations of the same compiler, can legally lay the same bitfield struct out differently. That is fatal for a format one device writes and another reads, or a format that has to survive a firmware update on the same device.
• Decouple the wire format from host byte order. Pick one byte order for storage (big-endian here) and convert to and from it explicitly with byte-at-a-time helpers, so the packed record is portable between a little-endian microcontroller and a big-endian one, and safe to store in flash and reread after the code around it has been relinked at a different address.

#include <stdint.h>

#define SENSOR_ID_MASK 0x3Fu
#define FLAGS_MASK     0x0Fu
#define HUM_MASK       0x3FFu
#define TEMP_MASK      0xFFFu

typedef struct {
    int16_t  temperature;
    uint16_t humidity;
    uint8_t  flags;
    uint8_t  sensor_id;
} sensor_record_t;

static uint32_t pack_record(const sensor_record_t *r) {
    uint32_t temp = (uint32_t)((uint16_t)r->temperature) & TEMP_MASK;
    uint32_t hum  = (uint32_t)r->humidity & HUM_MASK;
    uint32_t flg  = (uint32_t)r->flags & FLAGS_MASK;
    uint32_t id   = (uint32_t)r->sensor_id & SENSOR_ID_MASK;
    return (id << 26) | (flg << 22) | (hum << 12) | temp;
}

static void unpack_record(uint32_t packed, sensor_record_t *out) {
    out->sensor_id = (uint8_t)((packed >> 26) & SENSOR_ID_MASK);
    out->flags     = (uint8_t)((packed >> 22) & FLAGS_MASK);
    out->humidity  = (uint16_t)((packed >> 12) & HUM_MASK);
    uint32_t t = packed & TEMP_MASK;
    if (t & (1u << 11)) t |= ~TEMP_MASK;   /* sign-extend the 12-bit field */
    out->temperature = (int16_t)t;
}

static void write_be32(uint8_t *buf, uint32_t v) {
    buf[0] = (uint8_t)(v >> 24); buf[1] = (uint8_t)(v >> 16);
    buf[2] = (uint8_t)(v >> 8);  buf[3] = (uint8_t)(v);
}

static uint32_t read_be32(const uint8_t *buf) {
    return ((uint32_t)buf[0] << 24) | ((uint32_t)buf[1] << 16) |
           ((uint32_t)buf[2] << 8)  | (uint32_t)buf[3];
}

#include <stdio.h>
int main(void) {
    sensor_record_t original = { .temperature = -137, .humidity = 612, .flags = 0b1010, .sensor_id = 41 };
    uint32_t packed = pack_record(&original);
    uint8_t wire[4];
    write_be32(wire, packed);
    printf("packed word: 0x%08X\n", packed);
    printf("wire bytes: %02X %02X %02X %02X\n", wire[0], wire[1], wire[2], wire[3]);

    sensor_record_t decoded;
    unpack_record(read_be32(wire), &decoded);
    printf("decoded: temperature=%d humidity=%u flags=%u sensor_id=%u\n",
           decoded.temperature, decoded.humidity, decoded.flags, decoded.sensor_id);
    printf("roundtrip match: %s\n",
           (decoded.temperature == original.temperature && decoded.humidity == original.humidity &&
            decoded.flags == original.flags && decoded.sensor_id == original.sensor_id) ? "yes" : "no");
    printf("sizeof(packed word) = %zu bytes\n", sizeof(packed));
    printf("sizeof(sensor_record_t one-field-per-byte-ish struct) = %zu bytes\n", sizeof(sensor_record_t));
    return 0;
}

Key points

• Each mask isolates exactly one field's bit width: & 0x3F (6 bits), & 0xF (4 bits), & 0x3FF (10 bits), & 0xFFF (12 bits).
• Reading a signed sub-word field needs manual sign extension: if the field's own sign bit is set (bit 11 of the 12-bit temperature), OR in the complement of that field's mask to fill the high bits with ones before casting to the wider signed type.
• The wire format and the in-memory format are deliberately separate: pack_record/unpack_record work on a host uint32_t, and write_be32/read_be32 convert that to and from a fixed big-endian byte sequence, so host byte order never leaks into what's actually stored.

Worked example

Packing { temperature: -137, humidity: 612, flags: 0b1010, sensor_id: 41 } and running it through pack_record then write_be32, then back through read_be32 and unpack_record, prints:

packed word: 0xA6A64F77
wire bytes: A6 A6 4F 77
decoded: temperature=-137 humidity=612 flags=10 sensor_id=41
roundtrip match: yes
sizeof(packed word) = 4 bytes
sizeof(sensor_record_t one-field-per-byte-ish struct) = 6 bytes

The decoded values match the originals exactly, including the negative temperature surviving the sign-extension step, and the measured struct sizes (4 bytes packed vs 6 bytes unpacked, no padding needed in the unpacked layout on this build) confirm the memory-savings claim above with real numbers rather than an assumed one.

Trade-offs & pitfalls

Complexity / cost trade-off

Memory: $\frac{6 - 4}{6} \approx 33\%$ smaller per record, which barely matters for one record but is the entire point once you're buffering thousands of records in RAM or writing millions to flash. CPU: every packed-field access costs a shift plus a mask (and, for the signed field, a conditional sign-extend) versus a single load for a per-byte layout; on a modern 32-bit microcontroller these are single-cycle arithmetic logic unit (ALU) operations and are negligible next to typical sensor sampling rates, though a very tight, very high-frequency interrupt handler is worth measuring rather than assuming.

Edge cases

• Endianness: casting a raw uint8_t buf[4] directly to a uint32_t * and dereferencing it bakes in host byte order; a record written on a little-endian device and read on a big-endian one would silently corrupt every field. The explicit byte-at-a-time read_be32/write_be32 pair avoids this entirely.
• Alignment: many 32-bit microcontrollers fault on an unaligned multi-byte load, for example reading a uint32_t from an address that isn't a multiple of 4. Because this design only ever touches the byte buffer one byte at a time (through read_be32/write_be32) and only forms a uint32_t value in a local variable, it stays safe even when the 4-byte buffer itself isn't naturally aligned in flash; a naive pointer cast to uint32_t * would not be.
• Sign-extension bugs: forgetting the sign-extend step turns any negative reading into a large positive number once the top bit of the 12-bit field is masked out and left there; testing at least one negative value, as this example does with -137, catches this immediately.
• Flag drift: since the 4 flag bits are distinguished only by position, name each one with an explicit constant (for example FLAG_CALIBRATED = 1 << 0) rather than magic numbers, or a later firmware revision that reorders them silently breaks every record written by the previous version.

Direct answer

A stack is last-in-first-out (LIFO): the most recently added item comes out first. A queue is first-in-first-out (FIFO): items come out in the order they arrived. Use a stack when you need to undo or backtrack in reverse arrival order, such as a browser's back button or a function call stack; use a queue when arrival order must be preserved, such as a task scheduler or a print spooler. You can build a queue out of two stacks: push is $O(1)$ worst case, and pop is amortized (averaged over a sequence of operations) $O(1)$ because each element only ever moves between the two stacks once over its lifetime.

Structured elaboration

Queue from two stacks. Keep an in_stack that absorbs pushes and an out_stack that serves pops. Pushing always goes to in_stack in $O(1)$. When a pop or peek is requested and out_stack is empty, drain all of in_stack into out_stack; this reverses the order, so the oldest element (which was at the bottom of in_stack) ends up on top of out_stack, ready to be returned first.

Why the amortized argument holds. Use the aggregate method: over any sequence of n operations, each element is pushed onto in_stack exactly once (cost 1), moved from in_stack to out_stack at most once in its lifetime (cost 1), and popped from out_stack exactly once (cost 1). No element is ever moved more than that, so the total work across the whole sequence is bounded by a constant multiple of n, which is what "amortized $O(1)$ per operation" means, even though any single pop that triggers the drain costs $O(n)$ by itself.

Worked example

class QueueFromStacks:
    def __init__(self):
        self.in_stack: list[int] = []
        self.out_stack: list[int] = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]


if __name__ == "__main__":
    q = QueueFromStacks()
    q.push(1)
    q.push(2)
    q.push(3)
    seq = [q.pop(), q.peek()]
    q.push(4)
    seq += [q.pop(), q.pop(), q.pop()]
    print(seq)

Running this prints [1, 2, 2, 3, 4]. The first pop() triggers a drain (in_stack [1,2,3] becomes out_stack [3,2,1], top popped is 1); peek() then reads 2 for free from the already-drained out_stack; pushing 4 goes straight to in_stack without disturbing out_stack; the remaining pops (2, 3) come from out_stack, and the last pop (4) triggers a second drain since out_stack had emptied.

Complexity

Space: $O(n)$ total across the two internal stacks, since every pushed element lives in exactly one of them at any time (no extra space is used beyond storing the n elements themselves).

Edge cases

• Calling pop() or peek() on an empty two-stack queue: in the reference implementation, _transfer() leaves out_stack empty when both stacks are empty, so pop()'s self.out_stack.pop() and peek()'s self.out_stack[-1] both raise an unhandled IndexError instead of failing cleanly. Guard this explicitly, for example if not self.in_stack and not self.out_stack: raise IndexError("pop from empty queue") before touching out_stack, so the caller gets a clear, intentional signal rather than an incidental one.
• A single push followed immediately by a pop: the drain moves that one element from in_stack to out_stack and it is returned, leaving both stacks empty again, which is the state the empty-queue guard above must handle correctly on the next call.

Trade-offs & pitfalls

The most common confusion is treating "amortized" as "always fast": a single pop can still cost $O(n)$ when it triggers the drain. Note the asymmetry with building a stack out of a single queue by rotating on every push (dequeue-then-requeue the previous elements so the newest sits at the front): that rotation happens on every single push, not just occasionally, so it is genuinely $O(n)$ per push with no amortization to appeal to, unlike the two-stack construction above where the expensive transfer is rare and each element only ever pays for it once.

Direct answer

Breadth-first search (BFS) visits a graph level by level using a first-in-first-out queue: it fully explores every node at the current distance from the source before moving one edge farther out, which is exactly why the first time BFS reaches a node, it has found a shortest path to it in edge count (for unweighted graphs). Depth-first search (DFS) instead follows one path as far as it can, using a stack (explicit or via recursion), only backtracking once it hits a dead end. Both run in $O(V + E)$ time and $O(V)$ space on an adjacency-list graph with $V$ vertices and $E$ edges; reach for BFS when you need shortest paths or level-order information, and for DFS when you need to explore structure like cycles, connectivity, or an ordering that depends on finishing an entire subtree first, as in topological sort.

Structured elaboration

Mechanics

• BFS: enqueue the source, mark it visited, then repeatedly dequeue a node, and for each unvisited neighbor, mark it visited and enqueue it. The queue's contents at any point are exactly the current "frontier" one edge past the last fully-processed layer.
• DFS: push the source (or call recursively), mark it visited, and for each unvisited neighbor, recurse (or push) immediately, only returning to try the next neighbor after that whole branch is exhausted.
• Marking a node visited at the moment it's enqueued (BFS) or entered (DFS), not when it's dequeued or finished, avoids adding the same node to the queue or stack more than once.

Recursive versus iterative DFS

Recursive DFS is simpler to write, since the call stack does the bookkeeping for you, but it risks a stack overflow on a very deep graph (recursion depth is bounded by the language's call-stack limit, for example Python's default recursion limit of 1000). Iterative DFS with an explicit stack avoids that limit, at the cost of manually tracking which neighbors of a node remain to be visited.

Deep-and-narrow versus wide-and-shallow graphs

Both algorithms are $O(V)$ space in the worst case, but the shape of the graph determines which one actually uses less memory in practice: on a long, narrow chain, DFS's memory stays proportional to the current depth, which can be far less than BFS's frontier at the widest level; on a short, very wide graph (many nodes one edge from the source), BFS's frontier can be large while DFS's stack stays shallow. Neither algorithm is unconditionally more memory-efficient; it depends on the graph's shape.

Cycle detection and topological sort

A DFS-based topological sort (or cycle check) needs three states per node, not a single visited flag: unvisited, in-progress (currently on the recursion stack), and finished. An edge to an in-progress node is a back edge and signals a cycle; an edge to an already-finished node is fine and doesn't indicate one. A binary visited flag can't tell these two cases apart.

Worked example

from collections import deque

adj = {0: [1, 2], 1: [3], 2: [3], 3: []}


def bfs(start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return order


def dfs(start):
    visited = set()
    order = []

    def visit(u):
        visited.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in visited:
                visit(v)

    visit(start)
    return order


if __name__ == "__main__":
    print("BFS:", bfs(0))
    print("DFS:", dfs(0))

Running this prints BFS: [0, 1, 2, 3] and DFS: [0, 1, 3, 2]. BFS visits both of node 0's neighbors (1 and 2) before going any deeper, reaching 3 only after the whole first layer is done. DFS instead commits to the first neighbor, 1, follows it all the way to 3, then backtracks and only picks up 2 afterward.

Trade-offs & pitfalls

• DFS does not generally find shortest paths in edge count; only BFS gives that guarantee on unweighted graphs.
• Forgetting to mark a node visited until it's dequeued (rather than when it's enqueued) in BFS lets the same node be enqueued multiple times through different neighbors, wasting work even though the final result stays correct once a visited check also guards processing.
• For weighted graphs where edge costs differ, neither plain BFS nor DFS finds the shortest path by cost; that needs Dijkstra's algorithm or A* search instead.
• A disconnected graph needs a traversal restarted from every unvisited node to cover every component; a single BFS or DFS call from one source only reaches that source's connected component.

Complexity

Time: $O(V + E)$ for both, since every vertex and every edge is examined once. Space: $O(V)$ for both (BFS's queue plus visited set; DFS's recursion stack or explicit stack plus visited set).

Edge cases

• Disconnected graphs: restart the traversal from each unvisited node to reach every component.
• Self-loops and multi-edges: a visited check naturally prevents a self-loop from causing infinite reprocessing.
• A single-node graph with no edges: both traversals just return that one node.