Skip to question
asic.fyi

Hardware interview practice

Find device-tree depth without recursion

EasyFirmware AlgorithmsSystemVerilog

Find the maximum depth of a device-node pool with fixed storage while rejecting out-of-range children, cycles, and shared children.

Starting point

Question code

typedef struct { uint8_t left, right; } node_t;
typedef enum { DEPTH_OK, DEPTH_EINVAL, DEPTH_ECORRUPT } depth_rc_t;
depth_rc_t tree_depth(const node_t *pool, uint8_t count,
                      uint8_t root, uint8_t *depth);
enum { NO_NODE = 0xFF, MAX_NODES = 31 };
Reviewed example

Work through one case

Input
nodes: 0->{1,2}, 1->{3}, 2->{}, 3->{}; root=0
Expected output
maximum_depth=3

The fixed work queue visits depths 1, 2, and 3; each reachable child appears exactly once and every index is in range.

What to cover

Requirements

  1. Validate pointers, count at most 31, and the root index before the empty-tree case.
  2. Use a fixed stack or queue carrying node depth; do not recurse or allocate.
  3. Reject every reachable node encountered twice, including cycles and shared children.
  4. Check each child index before reading it and leave the output unchanged on every error.
Continue practicing
Firmware AlgorithmsParse a bounded Roman board revisionFirmware AlgorithmsAdd decimal lists from a fixed poolFirmware AlgorithmsEnumerate calibration sums with fixed memory