Q022FreeFirmware
Find device-tree depth without recursion
Interview prompt
Question
Find the maximum depth of a device-node pool with fixed storage while rejecting out-of-range children, cycles, and shared children. A nonnull pool points to storage for count node_t objects, and depth points to a separate writable uint8_t object. The caller provides valid aligned object storage; validate null pointers, numeric bounds and reachable indices. NO_NODE is the empty-root sentinel even when count is nonzero. For root=NO_NODE, validate the pointers and count, then return depth zero without inspecting unreachable pool entries.
Candidate starting point
Implementation scaffold
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
typedef struct { uint8_t left, right; } node_t;
typedef enum { DEPTH_OK, DEPTH_EINVAL, DEPTH_ECORRUPT } depth_rc_t;
enum { NO_NODE = 0xFF, MAX_NODES = 31 };
depth_rc_t tree_depth(const node_t *pool, uint8_t count,
uint8_t root, uint8_t *depth) {
// TODO: validate, traverse with fixed storage, and commit depth on success.
}
Reviewed example
Trace one case
Input
nodes: 0->{1,2}, 1->{3}, 2->{}, 3->{}; root=0Expected output
maximum_depth=3The explicit stack visits nodes at depths 1, 2, and 3. Each reachable child appears once, and the maximum is committed after all indices validate.
What to cover
Requirements
- Reject null pool/depth or count above 31. Then handle root=NO_NODE as empty; otherwise reject root>=count before traversing.
- Use a fixed stack or queue carrying node depth; do not recurse or allocate.
- Reject every reachable node encountered twice, including cycles and shared children.
- Check each child index before reading it and leave the output unchanged on every error.