Embedded DSA Interview Questions: Trees and Binary Search Trees (Q154–Q188)

Part 5 of the seven-part Embedded Firmware DSA Interview Guide — 35 questions answered at full depth for embedded, firmware and senior technical roles.

Binary tree interview questions for embedded roles usually turn on one thing: whether you notice that recursion depth is a memory budget. Thirty-five questions on trees and binary search trees, covering the traversals, the rotations, and the reason a sorted const array in flash often beats all of them.

---

Binary tree interview questions for embedded roles

• Q154. What is a binary tree?
• Q155. What is a complete binary tree and why does the shape matter?
• Q156. What is a full binary tree?
• Q157. What is a strict binary tree, and how does it differ from full?
• Q158. What is a perfect binary tree?
• Q159. What is the difference between height and depth?
• Q160. What is preorder traversal and when do you use it?
• Q161. What is inorder traversal and why does it matter on a BST?
• Q162. What is postorder traversal and when do you need it?
• Q163. How do you do a level order traversal?
• Q164. Why are all three depth first traversals the same function?
• Q165. How do you traverse a tree without recursion?
• Q166. How do you rebuild a tree from its traversals?
• Q167. How do you count the nodes in a tree?
• Q168. How do you count the leaf nodes in a tree?
• Q169. How do you compute the height of a tree?
• Q170. How do you find the diameter of a binary tree?
• Q171. How do you find the lowest common ancestor?
• Q172. How do you serialize and deserialize a binary tree?
• Q173. Where are trees used in embedded systems?
• Q174. What property defines a binary search tree?
• Q175. How do you search a binary search tree?
• Q176. How do you insert into a binary search tree?
• Q177. How do you delete a node from a binary search tree?
• Q178. How do you find the inorder successor?
• Q179. How do you find the inorder predecessor?
• Q180. How does insertion order change the shape of a BST?
• Q181. How do you validate a binary search tree correctly?
• Q182. What is the balance factor and how does AVL use it?
• Q183. What is the worst case for a BST and what triggers it?
• Q184. AVL versus plain BST versus red-black: which do you pick?
• Q185. What is a red-black tree and what do its invariants guarantee?
• Q186. What are the time complexities of BST operations?
• Q187. Where are binary search trees actually used?
• Q188. What BST mistakes cost candidates the offer?

---

Questions 154 to 188, explained fully.

One tree is used throughout so you can follow every trace against the same picture:

                1
              /   \
             2     3
            / \     \
           4   5     6
              /
             7

---

Section 9: Trees

---

Q154. What is a binary tree?

Say this out loud A hierarchical structure where each node has at most two children, conventionally called left and right. There is exactly one root, every other node has exactly one parent, and there are no cycles. With n nodes there are always exactly n minus 1 edges.

The full explanation

typedef struct tnode {
    int           data;
    struct tnode *left;
    struct tnode *right;
} tnode_t;

Vocabulary you need to use correctly, because interviewers listen for it:

Key structural facts

• n nodes means exactly n minus 1 edges, because every node except the root is reached by exactly one edge.
• Maximum nodes at level d is 2^d.
• Maximum nodes in a tree of height h is 2^(h+1) - 1.
• Minimum height for n nodes is floor(log2(n)), achieved when the tree is as balanced as possible.
• Maximum height for n nodes is n - 1, when every node has one child, which is a linked list wearing a hat.

That last point is the whole reason balancing exists, and it comes back in Q183.

Why a tree at all

An array gives O(1) access but O(n) insertion. A linked list gives O(1) insertion but O(n) search. A balanced tree gives O(log n) for search, insert, and delete simultaneously. That is the trade being bought, and being able to state it in one sentence is the right way to open any tree answer.

---

Q155. What is a complete binary tree and why does the shape matter?

Say this out loud Every level is completely filled except possibly the last, and the last level is filled from the left with no gaps. This is the shape that allows an array representation with no pointers at all, which is why heaps are complete trees.

complete:              NOT complete (gap before the last node):
      1                        1
     / \                      / \
    2   3                    2   3
   / \ /                    /     \
  4  5 6                   4       6

The array representation, which is the entire point

For a node at index i, using 0 based indexing:

left child  = 2i + 1
right child = 2i + 2
parent      = (i - 1) / 2

The tree at the top of this file, if it were complete, would store as [1, 2, 3, 4, 5, 6]. No left and right pointers exist. On a 32 bit target that saves 8 bytes per node, so a 1000 node structure drops from 12 KB to 4 KB.

This only works because completeness guarantees there are no holes. One gap and the index arithmetic points at the wrong node.

/* a complete binary tree stored as a flat array */
static int tree[N];

static inline int left(int i)   { return 2*i + 1; }
static inline int right(int i)  { return 2*i + 2; }
static inline int parent(int i) { return (i - 1) / 2; }

Why it matters in firmware. No pointers, no allocation, contiguous memory, cache friendly, and the whole structure can be a const array in flash if it never changes. It is also the reason a binary heap is the standard priority queue: heap plus array equals a priority queue with zero overhead per element.

---

Q156. What is a full binary tree?

Say this out loud Every node has either zero children or exactly two. No node has exactly one child. It is also called a proper or strict binary tree.

full:                  NOT full (node 2 has one child):
      1                        1
     / \                      / \
    2   3                    2   3
   / \                      /
  4   5                    4

The property worth knowing: in a full binary tree, the number of leaves is always one more than the number of internal nodes. If L is leaves and I is internal nodes, then L = I + 1, so n = 2I + 1 and the total node count is always odd.

Quick proof sketch: each internal node contributes 2 edges, so there are 2I edges, and a tree with n nodes has n-1 edges, giving 2I = n - 1. With n = I + L that yields L = I + 1.

Where full trees appear. Expression trees, where every operator is binary and therefore has exactly two operands, and every leaf is a value. Huffman coding trees have the same property, which is why the leaf count relationship matters when sizing the node array.

---

Q157. What is a strict binary tree, and how does it differ from full?

Same thing as full. “Strict”, “proper”, and “full” are three names for the identical property: degree is 0 or 2, never 1.

The terminology is genuinely inconsistent across textbooks, which is why this appears as two separate questions in the bank. Some older texts, particularly American ones, use “full” to mean what everyone else calls “perfect”. The safe move in an interview is to state the definition you are using before answering:

“By full or strict I mean every node has zero or two children. If you mean the one where every level is completely filled, that is what I would call perfect.”

Naming the ambiguity rather than guessing is the correct response, and it costs one sentence.

---

Q158. What is a perfect binary tree?

Say this out loud Every internal node has exactly two children and all leaves are at the same depth. It is both full and complete, and it is the most constrained of the four shapes.

perfect, height 2:
       1
      / \
     2   3
    / \ / \
   4  5 6  7

The exact counts, which is why perfect trees are useful for reasoning

For a perfect tree of height h:

The insight that matters: more than half the nodes are leaves. In a perfect tree, 2^h of the 2^(h+1) - 1 nodes are leaves, which is just over 50 percent. That is why algorithms that do work proportional to leaf count are not cheaper than ones that touch every node, and it is why building a heap bottom up is O(n) rather than O(n log n): the many nodes near the bottom sift down only a short distance.

The relationship between the four shapes

perfect  =>  complete  AND  full
complete  does not imply  full
full      does not imply  complete

Being able to give a counterexample for each direction is the follow up they will ask.

---

Q159. What is the difference between height and depth?

Say this out loud Depth is measured downward from the root, height is measured upward from the leaves. The root has depth 0, a leaf has height 0, and the height of the tree is the height of the root. The convention matters because some texts count nodes instead of edges, which shifts every answer by one.

On the reference tree

                1        depth 0, height 3
              /   \
             2     3     depth 1;  2 has height 2,  3 has height 1
            / \     \
           4   5     6   depth 2;  4 has height 0,  5 has height 1,  6 has height 0
              /
             7           depth 3, height 0

Tree height is 3, counting edges on the path 1 to 2 to 5 to 7.

The convention trap. Counting nodes instead of edges makes the same tree height 4, and makes an empty tree height 0 instead of -1. Both conventions appear in real textbooks. State which you are using in the first sentence of your answer. The edge convention is the more common one and makes a single node tree height 0, which is tidier.

Using -1 for empty is what makes the recursive height formula 1 + max(left, right) work without a special case, which is the practical argument for it.

---

Q160. What is preorder traversal and when do you use it?

Say this out loud Visit the node, then the left subtree, then the right subtree. Root first. It is the traversal that produces a structure you can rebuild the tree from directly, so it is what serialization uses.

void preorder(const tnode_t *n) {
    if (n == NULL) return;
    visit(n);                 /* NODE first */
    preorder(n->left);
    preorder(n->right);
}

Trace on the reference tree

visit 1
  go left to 2
    visit 2
      go left to 4, visit 4, no children, return
      go right to 5
        visit 5
          go left to 7, visit 7, return
          right is NULL
      return
  go right to 3
    visit 3
      left is NULL
      go right to 6, visit 6, return

output: 1 2 4 5 7 3 6

Uses

• Copying or cloning a tree, because you create the parent before its children need somewhere to attach.
• Serialization, Q172.
• Prefix notation for expression trees, so a + b becomes + a b.
• Any traversal where a node must be processed before its descendants, such as applying a permission or a transform that inherits downward.

---

Q161. What is inorder traversal and why does it matter on a BST?

Say this out loud Left subtree, then the node, then the right subtree. On a binary search tree this visits the keys in sorted ascending order, which is its defining use.

void inorder(const tnode_t *n) {
    if (n == NULL) return;
    inorder(n->left);
    visit(n);                 /* NODE in the middle */
    inorder(n->right);
}

Trace on the reference tree

descend to 4 (leftmost), visit 4
back at 2, visit 2
into 5's left, which is 7, visit 7
back at 5, visit 5
back at 1, visit 1
into 3's left, which is NULL
visit 3
into 6, visit 6

output: 4 2 7 5 1 3 6

The BST property. On a BST, everything in the left subtree is smaller and everything in the right is larger. Inorder therefore emits smaller, then self, then larger, recursively, which is exactly sorted order. This gives you an O(n) sorted iteration with no sorting step, and it is the basis of the validation trick in Q181.

Uses: sorted output from a BST, in-order successor and predecessor logic, and infix notation for expression trees, though infix requires parentheses to be unambiguous.

---

Q162. What is postorder traversal and when do you need it?

Say this out loud Left, right, then the node. Children are always processed before their parent, which makes it the correct traversal for freeing a tree, computing sizes and heights, and evaluating expression trees.

void postorder(const tnode_t *n) {
    if (n == NULL) return;
    postorder(n->left);
    postorder(n->right);
    visit(n);                 /* NODE last */
}

Trace on the reference tree

output: 4 7 5 2 6 3 1

Note the root comes last, always. And every child appears before its parent, always.

Freeing a tree is the canonical use, and it must be postorder

void tree_free(tnode_t *n) {
    if (n == NULL) return;
    tree_free(n->left);
    tree_free(n->right);
    free(n);                  /* free the node AFTER its children */
}

Freeing preorder would release the node first, and then n->left would be a read from freed memory. That is the question behind the question: “which traversal do you use to delete a tree, and why”. The answer is postorder, because you need the pointers before you destroy the node holding them.

The general principle to state: the position of the visit statement relative to the two recursive calls is the only difference between the three traversals. Where the work goes decides the order. That single sentence covers Q160, Q161, Q162, and Q164 at once.

---

Q163. How do you do a level order traversal?

Say this out loud Breadth first, visiting every node at depth d before any node at depth d plus 1. It uses a queue rather than recursion, because the order is not depth first and the call stack cannot express it naturally.

void level_order(tnode_t *root) {
    tnode_t *queue[MAX_NODES];
    int head = 0, tail = 0;

    if (root == NULL) return;
    queue[tail++] = root;

    while (head < tail) {
        tnode_t *n = queue[head++];
        visit(n);
        if (n->left)  queue[tail++] = n->left;
        if (n->right) queue[tail++] = n->right;
    }
}

Trace on the reference tree

Output: 1 2 3 4 5 6 7

The level-by-level variant, which is what most follow ups actually want:

while (head < tail) {
    int level_size = tail - head;          /* snapshot the count for THIS level */
    for (int i = 0; i < level_size; i++) {
        tnode_t *n = queue[head++];
        visit(n);
        if (n->left)  queue[tail++] = n->left;
        if (n->right) queue[tail++] = n->right;
    }
    printf("\n");                          /* end of this level */
}

Capturing level_size before the inner loop is the trick. It freezes the boundary so newly enqueued children belong to the next level rather than this one. This gives you level-by-level printing, tree height by counting iterations, and the right-side view by taking the last node of each level.

Memory note. The queue can hold up to the width of the widest level, which for a perfect tree is 2^h, roughly n/2. So level order needs O(n) space while depth first traversal needs only O(h). On a memory constrained target that difference decides which you use, and it is the reverse of what people expect.

---

Q164. Why are all three depth first traversals the same function?

The unified view. All three depth first traversals are the same function with the visit line moved:

void traverse(const tnode_t *n) {
    if (n == NULL) return;
    /* PREORDER  position */
    traverse(n->left);
    /* INORDER   position */
    traverse(n->right);
    /* POSTORDER position */
}

Why recursion fits trees so naturally. A tree is defined recursively: a tree is a node plus a left tree and a right tree. The code mirrors the definition exactly, which is why the recursive version is five lines and the iterative version is twenty.

Complexity, and the part people get wrong

• Time: O(n). Every node is visited exactly once, and each visit does O(1) work.
• Space: O(h), not O(n). The stack holds one frame per level on the current root-to-node path. For a balanced tree that is O(log n). For a degenerate tree it is O(n).

That distinction is a favourite question. The number of calls is n, but the maximum simultaneous depth is h, exactly as in Q88 for Fibonacci.

Why it matters in firmware. For a balanced tree, h is at most about 20 for a million nodes, so 20 frames at maybe 24 bytes each is 480 bytes. That is acceptable. For an unbalanced tree, h can equal n and the recursion overflows. So recursion on trees is safe only when the tree is guaranteed balanced, which means a self balancing structure or a static tree built at compile time. State that condition explicitly rather than saying “trees are shallow so recursion is fine”.

---

Q165. How do you traverse a tree without recursion?

Preorder, the easy one

void preorder_iter(tnode_t *root) {
    tnode_t *stack[MAX_H];
    int top = 0;
    if (root) stack[top++] = root;

    while (top > 0) {
        tnode_t *n = stack[--top];
        visit(n);
        if (n->right) stack[top++] = n->right;   /* right pushed FIRST */
        if (n->left)  stack[top++] = n->left;    /* so left pops first */
    }
}

Push right before left, so left is on top and comes out first. Reversing those two lines gives you a mirror image traversal, which is a subtle bug.

Inorder, the one worth practising

void inorder_iter(tnode_t *root) {
    tnode_t *stack[MAX_H];
    int top = 0;
    tnode_t *cur = root;

    while (cur != NULL || top > 0) {
        while (cur != NULL) {          /* go as far left as possible, stacking the path */
            stack[top++] = cur;
            cur = cur->left;
        }
        cur = stack[--top];            /* backtrack to the deepest unvisited node */
        visit(cur);
        cur = cur->right;              /* then handle its right subtree */
    }
}

The loop condition needs both parts. cur != NULL means there is more to descend into, top > 0 means there is unfinished business on the stack. Dropping either one truncates the traversal.

Postorder, the hard one

The problem, as in Q93, is that on popping a node you cannot tell whether you are arriving for the first time or returning after the children. Two standard solutions.

Solution A, two stacks, easy to remember:

/* push root, then repeatedly pop and push to stack2, pushing left then right.
   stack2 ends up in reverse postorder, so pop it all to get postorder. */

This works because visiting node, right, left and then reversing gives left, right, node. Clean, but it uses O(n) extra space for the second stack.

Solution B, one stack plus a last_visited pointer:

void postorder_iter(tnode_t *root) {
    tnode_t *stack[MAX_H];
    int top = 0;
    tnode_t *cur = root, *last = NULL;

    while (cur != NULL || top > 0) {
        while (cur != NULL) { stack[top++] = cur; cur = cur->left; }

        tnode_t *peek = stack[top - 1];
        if (peek->right != NULL && last != peek->right) {
            cur = peek->right;             /* right subtree not done yet */
        } else {
            visit(peek);
            last = peek;
            top--;
        }
    }
}

last records the node most recently visited. If it is the current node’s right child, the right subtree is finished and the node itself can be visited. That comparison is the hand rolled replacement for the return address.

Morris traversal, worth naming. Inorder traversal in O(1) space by temporarily rewriting null right pointers of predecessors into links back to the current node, then undoing them. Genuinely useful when memory is the binding constraint, but it mutates the tree during traversal so it is not safe if another context can read the tree concurrently. Mentioning that it exists, and that caveat, is a strong bonus.

Why iterative matters in firmware. The explicit stack is a fixed array whose size you set to the maximum expected height plus margin, and overflow is a testable condition returning an error. The call stack gives you neither.

---

Q166. How do you rebuild a tree from its traversals?

Say this out loud Preorder plus inorder uniquely determines a binary tree, and so does postorder plus inorder. Preorder plus postorder does not, unless the tree is full. The construction works because preorder gives you the root and inorder tells you where the left subtree ends.

The algorithm

1. The first element of preorder is the root.
2. Find that value in inorder. Everything to its left is the left subtree, everything to its right is the right subtree.
3. The left subtree’s size tells you how to split the preorder array too.
4. Recurse on both halves.

Worked example

preorder: 1 2 4 5 7 3 6
inorder:  4 2 7 5 1 3 6

Step 1: preorder[0] is 1, so 1 is the root. Find 1 in inorder, at index 4.

left  inorder:  [4 2 7 5]      4 elements
right inorder:  [3 6]          2 elements
left  preorder: [2 4 5 7]      the next 4 after the root
right preorder: [3 6]          the remaining 2

Step 2 on the left: preorder[0] is 2, root of the left subtree. In inorder [4 2 7 5], 2 is at index 1.

left  of 2: inorder [4],     preorder [4]
right of 2: inorder [7 5],   preorder [5 7]

Continue and you reconstruct the reference tree exactly.

static tnode_t *build(const int *pre, int *pre_idx,
                      const int *in, int in_lo, int in_hi) {
    if (in_lo > in_hi) return NULL;

    int root_val = pre[(*pre_idx)++];
    tnode_t *root = node_alloc(root_val);

    int mid = in_lo;
    while (in[mid] != root_val) mid++;          /* O(n) scan, see the note below */

    root->left  = build(pre, pre_idx, in, in_lo, mid - 1);
    root->right = build(pre, pre_idx, in, mid + 1, in_hi);
    return root;
}

Complexity. The linear scan for the root makes this O(n squared) in the worst case. Replacing it with a hash map from value to inorder index makes it O(n). That optimisation is the follow up they will ask for.

Why preorder plus postorder is insufficient. Consider a root with a single child. Preorder is root, child and postorder is child, root regardless of whether the child is left or right. There is no information distinguishing the two, so the tree is not unique. If the tree is guaranteed full, no node has a single child and the ambiguity disappears.

---

Q167. How do you count the nodes in a tree?

int count_nodes(const tnode_t *n) {
    if (n == NULL) return 0;
    return 1 + count_nodes(n->left) + count_nodes(n->right);
}

O(n) time, O(h) space. This is postorder in shape: both children are computed before the node contributes its own 1.

The interesting variant, counting a complete tree in O(log squared n)

For a complete binary tree you can do better than O(n). Compare the height reached by going all the way left with the height going all the way right:

int count_complete(tnode_t *n) {
    if (n == NULL) return 0;

    int lh = 0, rh = 0;
    for (tnode_t *p = n; p; p = p->left)  lh++;
    for (tnode_t *p = n; p; p = p->right) rh++;

    if (lh == rh) return (1 << lh) - 1;      /* PERFECT subtree, use the formula */

    return 1 + count_complete(n->left) + count_complete(n->right);
}

If the leftmost and rightmost paths have equal length, the subtree is perfect and its node count is 2^h - 1 with no traversal at all. Otherwise recurse, and at each level exactly one of the two children is perfect, so only one branch continues deeply. That gives O(log n) levels times O(log n) height measurement, so O(log squared n).

Offering this unprompted after giving the O(n) version is a strong answer.

---

Q168. How do you count the leaf nodes in a tree?

int count_leaves(const tnode_t *n) {
    if (n == NULL) return 0;
    if (n->left == NULL && n->right == NULL) return 1;    /* both children absent */
    return count_leaves(n->left) + count_leaves(n->right);
}

The base cases must be in that order. Checking for the leaf condition before the null check would dereference a null pointer. Checking null first and returning 0 handles both the empty tree and the missing child of a one-child node.

Related counts, worth being able to produce quickly

/* nodes with exactly one child */
int count_half(const tnode_t *n) {
    if (n == NULL) return 0;
    int self = ((n->left == NULL) != (n->right == NULL)) ? 1 : 0;   /* XOR of presence */
    return self + count_half(n->left) + count_half(n->right);
}

/* nodes with exactly two children, the internal nodes of a full tree */
int count_full(const tnode_t *n) {
    if (n == NULL) return 0;
    int self = (n->left && n->right) ? 1 : 0;
    return self + count_full(n->left) + count_full(n->right);
}

The identity from Q156 gives you a free sanity check: in a tree with no single-child nodes, leaves equal two-child nodes plus one.

---

Q169. How do you compute the height of a tree?

int height(const tnode_t *n) {
    if (n == NULL) return -1;                  /* edge convention */
    int lh = height(n->left);
    int rh = height(n->right);
    return 1 + (lh > rh ? lh : rh);
}

Returning -1 for the empty tree is what makes the formula work with no special case: a leaf gets 1 + max(-1, -1) which is 0, exactly as the edge convention requires. Returning 0 for empty gives you the node convention, where a leaf has height 1.

O(n) time, O(h) space.

The iterative version, using level order

int height_iter(tnode_t *root) {
    if (root == NULL) return -1;
    tnode_t *q[MAX_NODES];
    int head = 0, tail = 0, h = -1;
    q[tail++] = root;

    while (head < tail) {
        int level_size = tail - head;
        h++;
        for (int i = 0; i < level_size; i++) {
            tnode_t *n = q[head++];
            if (n->left)  q[tail++] = n->left;
            if (n->right) q[tail++] = n->right;
        }
    }
    return h;
}

Each pass of the outer loop consumes exactly one level, so counting the passes gives the height. This is the level-size snapshot trick from Q163 reused.

The balance check, which is where this usually leads

The naive version calls height at every node, making it O(n squared):

bool is_balanced_slow(const tnode_t *n) {
    if (n == NULL) return true;
    int diff = height(n->left) - height(n->right);
    if (diff < -1 || diff > 1) return false;
    return is_balanced_slow(n->left) && is_balanced_slow(n->right);
}

The O(n) version computes the height and the balance verdict in the same pass, using a sentinel to propagate failure:

static int check(const tnode_t *n) {
    if (n == NULL) return -1;
    int lh = check(n->left);
    if (lh == -2) return -2;                /* already unbalanced below, propagate */
    int rh = check(n->right);
    if (rh == -2) return -2;
    if (lh - rh > 1 || rh - lh > 1) return -2;
    return 1 + (lh > rh ? lh : rh);
}
bool is_balanced(const tnode_t *n) { return check(n) != -2; }

Recognising that the recomputation is the problem, and fixing it by returning two pieces of information from one traversal, is the actual skill being tested. The same pattern appears again in Q170.

---

Q170. How do you find the diameter of a binary tree?

Say this out loud The diameter is the number of edges on the longest path between any two nodes. That path may or may not pass through the root. At each node, the longest path through that node is the left height plus the right height plus 2, and the answer is the maximum of that over all nodes. Computing height and diameter in a single traversal makes it O(n).

static int diameter_helper(const tnode_t *n, int *best) {
    if (n == NULL) return -1;                       /* height of empty */

    int lh = diameter_helper(n->left,  best);
    int rh = diameter_helper(n->right, best);

    int through_here = lh + rh + 2;                 /* edges: lh+1 down left, rh+1 down right */
    if (through_here > *best) *best = through_here;

    return 1 + (lh > rh ? lh : rh);                 /* height, for my parent */
}

int diameter(const tnode_t *root) {
    int best = 0;
    diameter_helper(root, &best);
    return best;
}

The key structural insight, and this is the point of the question: each node returns its height to its parent while simultaneously updating a running maximum through a pointer. One value goes up the recursion, another accumulates sideways. The naive approach computes height separately at every node and costs O(n squared).

On the reference tree

At node 2: left height is 0 (node 4), right height is 1 (node 5 with child 7). Path through 2 is 0 + 1 + 2 = 3 edges, namely 4 to 2 to 5 to 7.

At node 1: left height is 2, right height is 1. Path through 1 is 2 + 1 + 2 = 5 edges, namely 7 to 5 to 2 to 1 to 3 to 6.

Diameter is 5.

The +2 explanation. lh is the height of the left subtree, so the distance from the current node down to that deepest left node is lh + 1 edges. Same on the right. Add them: (lh + 1) + (rh + 1). If you use the node counting convention instead, the constant changes, which is another reason to state your convention up front.

---

Q171. How do you find the lowest common ancestor?

Say this out loud The deepest node that has both target nodes as descendants, where a node counts as a descendant of itself. For a general binary tree it is an O(n) postorder search. For a BST it is much simpler, an O(h) walk down using the ordering.

General binary tree

tnode_t *lca(tnode_t *n, tnode_t *p, tnode_t *q) {
    if (n == NULL || n == p || n == q) return n;

    tnode_t *l = lca(n->left,  p, q);
    tnode_t *r = lca(n->right, p, q);

    if (l && r) return n;          /* found one on each side: THIS node is the LCA */
    return (l != NULL) ? l : r;    /* both on one side, or neither found */
}

How to explain it. The function returns “the LCA if I found it in my subtree, otherwise whichever target I found, otherwise NULL”. If a node gets a non-null answer from both children, the two targets are in different subtrees, so the split happens here and this node is the answer. If both came from one side, that side’s answer propagates upward unchanged.

On the reference tree, LCA of 4 and 7:

node 4 returns 4 (matches p)
node 7 returns 7 (matches q)
node 5: left returns 7, right returns NULL -> returns 7
node 2: left returns 4, right returns 7 -> BOTH non-null -> returns 2
node 1: left returns 2, right returns NULL -> returns 2

Answer: 2. Correct.

The BST version, O(h) and much simpler

tnode_t *lca_bst(tnode_t *n, int p, int q) {
    while (n != NULL) {
        if (p < n->data && q < n->data)      n = n->left;    /* both smaller */
        else if (p > n->data && q > n->data) n = n->right;   /* both larger */
        else return n;                                        /* they split here */
    }
    return NULL;
}

The first node where the two values fall on opposite sides, or where one equals the node, is the LCA. No recursion and no stack.

The caveat to state: the general version assumes both nodes are actually present. If one is absent it returns the other, which looks like a valid answer and is not. Verifying presence requires a second pass or a modified helper that also returns found flags. Interviewers frequently ask this as a follow up.

---

Q172. How do you serialize and deserialize a binary tree?

Say this out loud Preorder with explicit null markers uniquely determines the tree, so one traversal is enough for serialization and one pass rebuilds it. Without null markers you would need two traversals.

/* serialize: preorder, writing a sentinel for every absent child */
void serialize(const tnode_t *n, FILE *f) {
    if (n == NULL) { fprintf(f, "# "); return; }
    fprintf(f, "%d ", n->data);
    serialize(n->left, f);
    serialize(n->right, f);
}

/* deserialize: read in the same order */
tnode_t *deserialize(FILE *f) {
    char tok[16];
    if (fscanf(f, "%15s", tok) != 1) return NULL;
    if (tok[0] == '#') return NULL;

    tnode_t *n = node_alloc(atoi(tok));
    n->left  = deserialize(f);
    n->right = deserialize(f);
    return n;
}

The reference tree serializes to:

1 2 4 # # 5 7 # # # 3 # 6 # #

Why the null markers make it unique. Preorder alone is ambiguous, because 1 2 could mean 2 is the left child or the right child. The # resolves it: 1 2 # # says 1 has left child 2 and no right child, while 1 # 2 # # says 1 has no left child. Every node emits exactly two child slots, so the structure is fully encoded.

The size cost. A tree with n nodes emits n + 1 null markers, because a binary tree with n nodes has exactly n + 1 null links. So the serialized form is roughly 2n + 1 tokens.

The binary format for firmware

Text is wasteful. A compact form for flash storage:

/* one byte tag plus the payload */
#define TAG_NULL 0x00
#define TAG_NODE 0x01

void serialize_bin(const tnode_t *n, uint8_t *buf, size_t *off) {
    if (n == NULL) { buf[(*off)++] = TAG_NULL; return; }
    buf[(*off)++] = TAG_NODE;
    memcpy(&buf[*off], &n->data, sizeof n->data);   /* memcpy, for alignment */
    *off += sizeof n->data;
    serialize_bin(n->left,  buf, off);
    serialize_bin(n->right, buf, off);
}

Use memcpy rather than a pointer cast, for the alignment and strict aliasing reasons from the first file. And prefix the whole record with a version byte and follow it with a CRC, so a partially written flash record is detectable rather than silently loaded as a corrupt tree.

Why it matters in firmware. Persisting a configuration tree, a menu structure, or a decision tree to flash and restoring it at boot. The alternative, and often the better one, is to build the tree at compile time as a const array in flash so no deserialization is needed at all. Mention that alternative, because it is what a senior engineer would reach for first.

---

Q173. Where are trees used in embedded systems?

The firmware specific pattern worth describing: the static flash-resident tree.

typedef struct menu_item {
    const char             *label;
    void                  (*action)(void);
    const struct menu_item *first_child;
    const struct menu_item *next_sibling;
} menu_item_t;

static const menu_item_t settings_items[] = {
    { "Brightness", set_brightness, NULL, &settings_items[1] },
    { "Volume",     set_volume,     NULL, NULL },
};

static const menu_item_t root_items[] = {
    { "Settings", NULL, &settings_items[0], &root_items[1] },
    { "Status",   show_status, NULL, NULL },
};

Note the child-sibling representation rather than left and right. It handles arbitrary numbers of children with two pointers per node, and it is how a general tree is stored in binary tree form. The entire structure is const, so it lives in flash and costs zero RAM, it cannot be corrupted by a wild pointer, and there is no construction code at boot.

That last paragraph is a very strong thing to say in an embedded interview, because it shows you think about where data lives, not just what shape it has.

---

Section 10: Binary Search Tree

---

Q174. What property defines a binary search tree?

Say this out loud For every node, all keys in the left subtree are less than the node’s key and all keys in the right subtree are greater. The property is recursive, applying to every node and not just the root. An inorder traversal therefore produces the keys in sorted order, and that is the defining consequence.

        50
       /  \
     30    70
    /  \   /  \
  20   40 60   80

Inorder: 20 30 40 50 60 70 80. Sorted.

The recursive requirement is the trap. This is not a BST:

        50
       /  \
     30    70
    /  \
  20   60          <-- 60 > 50, so it must not be in the left subtree

Node 30 satisfies the local check, since 20 is less and 60 is greater. But 60 is in the left subtree of 50 and 60 is greater than 50, which violates the property at the root. Checking only immediate children is the classic wrong validation, and it is the subject of Q181.

Duplicate handling must be decided and stated. Three options: forbid duplicates, always place them left, or always place them right. Whichever you pick, the comparison in search, insert, and delete must be consistent with it, or lookups will miss entries. Interviewers ask this to see whether you notice an unspecified requirement.

Complexity

Every O(log n) here is conditional on balance, which no plain BST guarantees. That is Q183.

---

Q175. How do you search a binary search tree?

tnode_t *bst_search(tnode_t *n, int key) {
    while (n != NULL) {
        if      (key < n->data) n = n->left;
        else if (key > n->data) n = n->right;
        else return n;
    }
    return NULL;
}

Iterative, O(h) time, O(1) space. Write this version, not the recursive one: it is the same length and uses no stack.

Trace, searching for 40 in the tree above

at 50: 40 < 50, go left
at 30: 40 > 30, go right
at 40: equal, found

Three comparisons for seven nodes. In a balanced tree of a million nodes it would be about 20.

Why it is the same idea as binary search. Each comparison discards an entire subtree, which is half the remaining elements when the tree is balanced. The tree is a binary search over a structure that also supports O(log n) insertion, which an array does not.

Find min and max, which follow directly:

tnode_t *bst_min(tnode_t *n) { while (n && n->left)  n = n->left;  return n; }
tnode_t *bst_max(tnode_t *n) { while (n && n->right) n = n->right; return n; }

The smallest key is the leftmost node, the largest is the rightmost. Both O(h). These are used by delete and by successor, so they are worth writing separately.

---

Q176. How do you insert into a binary search tree?

bool bst_insert(tnode_t **root, int key) {
    tnode_t **pp = root;

    while (*pp != NULL) {
        if      (key < (*pp)->data) pp = &(*pp)->left;
        else if (key > (*pp)->data) pp = &(*pp)->right;
        else return false;                       /* duplicate, policy: reject */
    }

    tnode_t *n = node_alloc(key);
    if (!n) return false;
    *pp = n;                                     /* handles the empty tree identically */
    return true;
}

The pointer-to-pointer walk from the linked list section applies here too. pp ends up pointing at the null link where the new node belongs, whether that is the root pointer itself or a child pointer deep in the tree. No special case for the empty tree.

New nodes are always inserted as leaves. That is why insertion never restructures a plain BST, and also why the shape depends entirely on insertion order, which is the problem in Q180 and Q183.

Trace, inserting 45 into the earlier tree

at 50: 45 < 50, go left
at 30: 45 > 30, go right
at 40: 45 > 40, go right
right of 40 is NULL, attach here

Recursive version, for comparison:

tnode_t *bst_insert_rec(tnode_t *n, int key) {
    if (n == NULL) return node_alloc(key);
    if      (key < n->data) n->left  = bst_insert_rec(n->left,  key);
    else if (key > n->data) n->right = bst_insert_rec(n->right, key);
    return n;
}

Shorter, and the reassignment idiom n->left = insert(n->left, ...) is worth recognising because AVL and red-black insertion are written the same way, with rebalancing on the way back up. But it uses O(h) stack, so prefer the iterative version for a plain BST.

---

Q177. How do you delete a node from a binary search tree?

Say this out loud Three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children is replaced by its inorder successor, the smallest key in its right subtree, and then that successor is deleted from the right subtree, which is guaranteed to be an easier case.

Case 1: leaf

      50                50
     /  \              /  \
   30    70    -->   30    70        delete 20
  /  \              /  \
20    40           .    40

Set the parent’s link to NULL and free the node.

Case 2: one child

      50                50
     /  \              /  \
   30    70    -->   30    70        delete 20
  /                 /
20                15
  \
   15

The child takes the removed node’s place. The BST property holds automatically, because everything in that subtree was already on the correct side of the parent.

Case 3: two children. This is the case being tested.

      50                       60
     /  \                     /  \
   30    70       -->       30    70        delete 50
  / \   /  \               / \      \
20  40 60   80           20  40      80

You cannot simply remove 50, because both children need a parent. So:

1. Find the inorder successor, the smallest key in the right subtree, which is 60. It is the next key in sorted order.
2. Copy 60’s key into the node holding 50.
3. Delete the original 60 from the right subtree.

The successor is guaranteed to have no left child, because it is the leftmost node of that subtree. So step 3 is always case 1 or case 2, never case 3 again. The recursion terminates immediately.

tnode_t *bst_delete(tnode_t *n, int key) {
    if (n == NULL) return NULL;

    if      (key < n->data) n->left  = bst_delete(n->left,  key);
    else if (key > n->data) n->right = bst_delete(n->right, key);
    else {
        /* found it */
        if (n->left == NULL) {                     /* covers leaf and right-only */
            tnode_t *r = n->right;
            free(n);
            return r;
        }
        if (n->right == NULL) {                    /* left-only */
            tnode_t *l = n->left;
            free(n);
            return l;
        }
        /* two children */
        tnode_t *succ = bst_min(n->right);
        n->data = succ->data;                      /* copy the key up */
        n->right = bst_delete(n->right, succ->data);  /* remove the successor */
    }
    return n;
}

Handling left == NULL first collapses the leaf case and the right-only case into one branch, since returning n->right when it is also NULL correctly yields NULL.

You can use the predecessor instead, the largest key in the left subtree, and it is equally correct. Always using one or the other biases the tree’s shape over many deletions, so some implementations alternate. Mentioning that is a good detail.

Why it matters in firmware. Delete is the operation that makes people avoid trees on constrained targets. It is intricate, it has three cases, and getting it wrong corrupts the structure silently. If your workload is insert-and-lookup with rare deletion, a sorted const array in flash with binary search is simpler, faster, and cannot be corrupted. Say that.

---

Q178. How do you find the inorder successor?

Say this out loud The next node in sorted order. Two cases: if the node has a right subtree, the successor is the leftmost node of it. If not, the successor is the nearest ancestor for which this node lies in the left subtree.

Case A, there is a right subtree

tnode_t *successor_with_right(tnode_t *n) {
    n = n->right;
    while (n->left) n = n->left;
    return n;
}

The next larger key is the smallest key that is still larger, which is the minimum of the right subtree.

Case B, no right subtree. Walk down from the root.

tnode_t *successor(tnode_t *root, tnode_t *target) {
    if (target->right) {
        tnode_t *n = target->right;
        while (n->left) n = n->left;
        return n;
    }

    tnode_t *succ = NULL, *cur = root;
    while (cur != NULL) {
        if (target->data < cur->data) {
            succ = cur;                  /* candidate: remember it and go left */
            cur = cur->left;
        } else if (target->data > cur->data) {
            cur = cur->right;
        } else {
            break;
        }
    }
    return succ;
}

Each time you turn left, the node you turned away from is larger than the target and is the smallest such node seen so far. The last one recorded is the successor.

Example. In the tree with root 50, the successor of 40 is 50: 40 has no right child, and walking from 50 you go left at 50 (recording 50), then right at 30, then arrive at 40. The recorded candidate is 50. Correct.

With a parent pointer, case B becomes a walk upward: climb until you arrive at a node from its left child, and that node is the successor. That is cheaper but costs 4 bytes per node, which is the usual trade.

Where it is used. BST deletion (Q177), iterator implementations such as std::map::iterator++, and range queries.

---

Q179. How do you find the inorder predecessor?

The exact mirror image. If the node has a left subtree, the predecessor is the rightmost node of it. Otherwise it is the nearest ancestor for which this node lies in the right subtree.

tnode_t *predecessor(tnode_t *root, tnode_t *target) {
    if (target->left) {
        tnode_t *n = target->left;
        while (n->right) n = n->right;
        return n;
    }

    tnode_t *pred = NULL, *cur = root;
    while (cur != NULL) {
        if (target->data > cur->data) { pred = cur; cur = cur->right; }
        else if (target->data < cur->data) { cur = cur->left; }
        else break;
    }
    return pred;
}

Every left became right and every < became >. Being able to say “it is the mirror, so I swap the directions and the comparison” rather than rederiving it is the right response, and it saves interview time.

---

Q180. How does insertion order change the shape of a BST?

Insert each element in turn using Q176. The critical observation is that the shape depends entirely on the insertion order.

Sorted input produces the worst possible tree

Inserting 10, 20, 30, 40, 50:

10
  \
   20
     \
      30
        \
         40
           \
            50

Height 4 for 5 nodes. Every operation is O(n). This is a linked list with wasted pointers, and it is the single most important failure mode to be able to describe.

Balanced input produces a good tree

Inserting 30, 20, 40, 10, 50:

      30
     /  \
   20    40
  /        \
10          50

Height 2. Every operation is O(log n).

Building a perfectly balanced BST from a sorted array

If you already have sorted data, do not insert in order. Recurse on the middle:

tnode_t *build_balanced(const int *a, int lo, int hi) {
    if (lo > hi) return NULL;
    int mid = lo + (hi - lo) / 2;
    tnode_t *n = node_alloc(a[mid]);
    n->left  = build_balanced(a, lo, mid - 1);
    n->right = build_balanced(a, mid + 1, hi);
    return n;
}

O(n) time and a guaranteed minimum height. This is the correct answer whenever the data is known up front, and for firmware it is often the whole solution: build the balanced tree offline, emit it as a const array, and never insert at runtime at all.

---

Q181. How do you validate a binary search tree correctly?

Say this out loud Checking each node only against its immediate children is wrong, because the property is about entire subtrees. The correct approach passes a valid range down the recursion, narrowing it at each step. Alternatively, do an inorder traversal and verify the sequence is strictly increasing.

The wrong version, which is the point of the question

/* WRONG */
bool is_bst_wrong(const tnode_t *n) {
    if (n == NULL) return true;
    if (n->left  && n->left->data  >= n->data) return false;
    if (n->right && n->right->data <= n->data) return false;
    return is_bst_wrong(n->left) && is_bst_wrong(n->right);
}

This accepts the invalid tree from Q174, where 60 sits in the left subtree of 50. Every local check passes and the tree is still not a BST.

The range version, which is correct

static bool check_range(const tnode_t *n, long lo, long hi) {
    if (n == NULL) return true;
    if (n->data <= lo || n->data >= hi) return false;
    return check_range(n->left,  lo, n->data) &&
           check_range(n->right, n->data, hi);
}

bool is_bst(const tnode_t *root) {
    return check_range(root, LONG_MIN, LONG_MAX);
}

Descending left narrows the upper bound to the current key. Descending right raises the lower bound. So every node is checked against every ancestor’s constraint, not just its parent’s.

Using long for the bounds avoids the edge case where a node legitimately holds INT_MIN or INT_MAX and the sentinel comparison rejects it. Interviewers who plant that test case are checking whether you thought about the sentinels.

The inorder version, equally valid

bool is_bst_inorder(const tnode_t *n, long *prev) {
    if (n == NULL) return true;
    if (!is_bst_inorder(n->left, prev)) return false;
    if (n->data <= *prev) return false;          /* must be strictly increasing */
    *prev = n->data;
    return is_bst_inorder(n->right, prev);
}

Since inorder on a valid BST is sorted, checking that each key exceeds the previous one is a complete test. Both are O(n) time and O(h) space. Offering both, and explaining that they test the same property from two directions, is a strong answer.

---

Q182. What is the balance factor and how does AVL use it?

Say this out loud For a node, the balance factor is the height of its left subtree minus the height of its right subtree. An AVL tree keeps this in the range -1 to +1 at every node, and restores it with rotations whenever an insert or delete pushes it outside.

int balance_factor(const tnode_t *n) {
    if (n == NULL) return 0;
    return height(n->left) - height(n->right);
}

Computing it by calling height is O(n). A real AVL implementation stores the height, or just the balance factor in two bits, inside each node and updates it during the rebalance, making it O(1).

The four imbalance cases and their fixes

A right rotation, drawn

      z                      y
     / \                   /   \
    y   T4    -->         x     z
   / \                   / \   / \
  x   T3                T1 T2 T3 T4
 / \
T1  T2

tnode_t *rotate_right(tnode_t *z) {
    tnode_t *y  = z->left;
    tnode_t *T3 = y->right;

    y->right = z;                    /* y becomes the new root of this subtree */
    z->left  = T3;                   /* z adopts y's old right subtree */

    update_height(z);                /* z first, it is now the child */
    update_height(y);
    return y;                        /* the caller must reattach this */
}

Why the BST property survives. T3 held keys between y and z. After the rotation it sits as z’s left subtree, which is still the region between y and z. Nothing crosses a boundary. Being able to say that sentence is what separates understanding rotations from having memorised the picture.

Updating z’s height before y’s is mandatory, because y’s height depends on z’s new height.

---

Q183. What is the worst case for a BST and what triggers it?

Say this out loud Sorted or reverse sorted insertion produces a degenerate tree, a linked list, with height n minus 1 and O(n) for every operation. This is not a rare edge case: sorted input is extremely common, since data arrives from a sorted file, from an ordered database query, or from monotonically increasing timestamps or IDs.

That last point is the one that matters. If your BST is keyed by an incrementing message ID or a timestamp, every insertion is the worst case, permanently.

The consequences

The stack row is the firmware-specific danger. A recursive traversal of a degenerate tree does not merely run slowly, it overflows the task stack and corrupts a neighbour.

Mitigations, in order of preference for embedded work

1. Build it balanced offline and store it as a const array in flash (Q180). No runtime insertion means no degeneration is possible.
2. Use a self balancing tree, AVL or red-black, and accept the code complexity.
3. Use a hash table if you only need exact lookup and not ordered iteration.
4. Randomise the insertion order, which gives expected O(log n) but no guarantee.
5. Use a sorted array with binary search if the data is static, which is simpler and faster than any tree.

Option 5 is underrated and is frequently the correct engineering answer for firmware. A sorted const table in flash with lower_bound gives O(log n) lookup, zero RAM, zero allocation, no rebalancing code, and no possibility of structural corruption.

---

Q184. AVL versus plain BST versus red-black: which do you pick?

AVL versus plain BST

AVL versus red-black, the comparison they usually want

The one line summary: AVL is more strictly balanced so lookups are faster, red-black rebalances with a bounded constant number of rotations so modifications are cheaper and, importantly for real time work, bounded.

That bounded rotation count is the reason the Linux kernel uses red-black trees. A scheduler cannot tolerate an insertion that sometimes costs O(log n) rotations, because worst case latency is what it is judged on.

For firmware, the honest answer is that you rarely implement either. You use a static balanced structure, a hash table, or a sorted array. If you genuinely need a dynamic ordered map on a target, pull in a tested implementation rather than writing red-black deletion from memory, which is one of the most error-prone routines in common use.

---

Q185. What is a red-black tree and what do its invariants guarantee?

Say this out loud A BST where each node carries a colour bit, and five invariants together guarantee that no root-to-leaf path is more than twice as long as any other. That bounds the height at about 2 log n, and rebalancing needs at most a constant number of rotations.

The five rules

1. Every node is red or black.
2. The root is black.
3. Every leaf, meaning the null sentinel, is black.
4. A red node’s children are both black. So no two reds are adjacent.
5. Every path from a given node down to any of its descendant nulls contains the same number of black nodes. That count is the black height.

Why those rules bound the height. Rule 5 says every path has the same number of black nodes. Rule 4 says reds cannot be consecutive, so at worst a path alternates red and black, making it at most twice as long as an all-black path. Hence the longest path is at most twice the shortest, and the height is at most 2 log2(n+1).

Reproducing that two sentence argument is far more valuable than reciting the insertion cases, and it is what an interviewer is checking for.

Insertion sketch. Insert as a normal BST leaf and colour it red, since red does not change any black height. If the parent is black, you are done. If the parent is red, rule 4 is violated and you fix it based on the uncle’s colour: if the uncle is red, recolour the parent, uncle, and grandparent, then repeat at the grandparent. If the uncle is black, rotate. At most two rotations are ever needed, though recolouring can propagate up the tree.

Where you meet them. The Linux CFS scheduler keeps runnable tasks in a red-black tree keyed by virtual runtime, so picking the next task is the leftmost node. epoll, the kernel’s high resolution timers, and the virtual memory area map all use them. In C++, std::map, std::set, and their multi variants are red-black trees.

Knowing that std::map is a red-black tree, and that this is why it has ordered iteration while std::unordered_map does not, is a standard interview checkpoint.

---

Q186. What are the time complexities of BST operations?

The comparison that decides real designs

The decision rule to state: if the data is static, use a sorted array. If you need ordering or range queries with dynamic data, use a balanced tree. If you only need exact-match lookup, use a hash table. That single sentence answers most “which structure would you use” questions.

---

Q187. Where are binary search trees actually used?

• std::map and std::set, and TreeMap in Java. Ordered associative containers.
• Database indexes. B-trees and B+ trees, which are the disk-oriented generalisation with high fanout so that one node fills a disk block or a flash page.
• File systems. ext4 uses HTree for directories, Btrfs is named for its B-tree, and NTFS indexes directories with B-trees.
• Linux CFS scheduler. Red-black tree keyed by virtual runtime.
• Range and interval queries. Finding every event in a time window, or every timer expiring in the next tick.
• Symbol tables in compilers and linkers. Ordered iteration matters for deterministic output.
• IP routing and longest prefix match. Usually a trie or radix tree, which is a tree specialised for keys made of digits.
• Autocomplete and dictionary lookup. Again usually a trie.

The embedded angle worth stating. On a microcontroller, the B-tree variant matters more than the binary variant, because flash is written in pages. A B-tree node sized to one flash page minimises the number of page reads per lookup, which is the dominant cost. Any embedded file system or key-value store on NOR or NAND flash uses this idea. Mentioning that you would match the node size to the page size is a strong, concrete answer.

---

Q188. What BST mistakes cost candidates the offer?

A checklist of what actually costs candidates the offer.

1. Validating with only the immediate children. Q181. The most common single mistake in this section.
2. Forgetting the two-child delete case, or handling it with the wrong replacement node. The successor must be the minimum of the right subtree, and it must then be deleted from that subtree.
3. Not asking about duplicates. The policy changes every comparison.
4. Assuming O(log n) unconditionally. A plain BST gives no guarantee. Say “O(log n) if balanced, O(n) otherwise” every time.
5. Using recursion without mentioning the depth risk. For an embedded interview specifically, always note that a degenerate tree makes recursion depth O(n).
6. Losing the subtree during delete. Freeing a node before reading its child pointers, or forgetting to reattach the returned subtree to the parent.
7. Using int sentinels in range validation when the data can legitimately be INT_MIN or INT_MAX.
8. Not returning the new root. Insert and delete can change the root, so either return it or take a tnode_t **.
9. Writing the recursive search when the iterative one is the same length. It signals that you reach for recursion by reflex.
10. Not questioning whether a tree is the right structure at all. For static data, a sorted array in flash beats a BST on every metric that matters in firmware. Raising that yourself is the strongest possible answer.

---

Quick revision sheet, questions 154 to 188

---

---

All seven parts of the guide

• Part 1: C Fundamentals, Pointers and Memory — Q1 to Q35
• Part 2: Arrays and Strings — Q36 to Q73
• Part 3: Recursion and Linked Lists — Q74 to Q123
• Part 4: Stack and Queue — Q124 to Q153
• Part 5: Trees and Binary Search Trees — Q154 to Q188 (you are here)
• Part 6: Heap and Sorting — Q189 to Q218
• Part 7: Hashing and Complexity — Q219 to Q248

Start here: The Embedded Firmware DSA Interview Guide, all 248 questions indexed in one place. Architecture round: Firmware Architecture Interview Questions: 100 Q&A.

---

Work with us

Kalapi Infotech builds firmware for connected embedded products — architecture and BSP work, RTOS and bare-metal development, secure boot and OTA infrastructure. If you are hiring for these roles, or building a product that needs them, we would be glad to talk.

Get in touch with our firmware team →