← C

Stacks, Queues & Trees

← Stacks, Queues & Trees

Select a question from the sidebar

15 questions in this topic

Question 1 / 15

How do you implement a stack using an array in C?

A stack is a Last-In-First-Out (LIFO) data structure. An array-based stack uses:

A fixed-size array to store elements
A top index that tracks the position of the topmost element (-1 means empty)

Operations:

push: Increment top, place element at arr[top]. O(1)
pop: Return arr[top], decrement top. O(1)
peek: Return arr[top] without modifying top. O(1)
isEmpty: Check if top == -1. O(1)
isFull: Check if top == capacity - 1. O(1)

Advantages: Simple, cache-friendly (contiguous memory), no allocation overhead per operation. Disadvantages: Fixed size (must know max capacity), or use realloc for dynamic sizing.

Pseudo Code

Stack structure:
  int arr[MAX]
  int top = -1

Push(stack, value):
  if top == MAX-1: overflow error
  top++
  arr[top] = value

Pop(stack):
  if top == -1: underflow error
  value = arr[top]
  top--
  return value

Peek(stack):
  if top == -1: error
  return arr[top]

Code

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int arr[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int val) {
    if (isFull(s)) {
        fprintf(stderr, "Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = val;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Stack underflow\n");
        return -1;  /* sentinel value */
    }
    return s->arr[(s->top)--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Stack is empty\n");
        return -1;
    }
    return s->arr[s->top];
}

int main(void) {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Top: %d\n", peek(&s));   /* 30 */
    printf("Pop: %d\n", pop(&s));    /* 30 */
    printf("Pop: %d\n", pop(&s));    /* 20 */
    printf("Empty: %d\n", isEmpty(&s));  /* 0 (false) */
    printf("Pop: %d\n", pop(&s));    /* 10 */
    printf("Empty: %d\n", isEmpty(&s));  /* 1 (true) */

    return 0;
}

Top: 30
Pop: 30
Pop: 20
Empty: 0
Pop: 10
Empty: 1

Key Points

•top = -1 means empty stack
•All operations (push, pop, peek) are O(1)
•Array-based stack has fixed capacity -- must check for overflow
•LIFO: last element pushed is the first one popped
•Cache-friendly due to contiguous memory

Gotchas

•Using sentinel value -1 for error on pop is ambiguous if -1 is a valid data value
•Stack overflow (top == MAX-1) silently dropping data if not handled
•Pre-increment vs post-increment on top: s->arr[++s->top] = val (push) vs s->arr[s->top--] (pop)
•Fixed size means you must know the maximum capacity in advance

Array with top index (-1 = empty). Push: arr[++top] = val. Pop: return arr[top--]. All ops O(1). Fixed capacity.

•top = -1 means empty, all ops O(1)

typedef struct { int arr[100]; int top; } Stack;
void initStack(Stack *s) { s->top = -1; }
void push(Stack *s, int v) { s->arr[++(s->top)] = v; }
int pop(Stack *s) { return s->arr[(s->top)--]; }
int peek(Stack *s) { return s->arr[s->top]; }
int isEmpty(Stack *s) { return s->top == -1; }

No overflow/underflow check in minimal version -- always add guards in production

Question 2 / 15

How do you implement a stack using a linked list in C?

A linked-list-based stack uses the head of the list as the top of the stack. Push inserts at head, pop removes from head.

Advantages over array-based:

No fixed capacity -- grows dynamically
No wasted memory from pre-allocated array

Disadvantages:

malloc/free overhead per push/pop
Not cache-friendly (nodes scattered in memory)
Extra memory per element (pointer overhead)

Operations: All O(1) -- always operate at the head.

Pseudo Code

Push(top, value):
  new = createNode(value)
  new->next = *top
  *top = new

Pop(top):
  if *top is NULL: underflow
  temp = *top
  value = temp->data
  *top = temp->next
  free(temp)
  return value

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
    int size;
} Stack;

void initStack(Stack *s) {
    s->top = NULL;
    s->size = 0;
}

int isEmpty(Stack *s) {
    return s->top == NULL;
}

void push(Stack *s, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) { perror("malloc"); exit(1); }
    newNode->data = val;
    newNode->next = s->top;
    s->top = newNode;
    s->size++;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Stack underflow\n");
        exit(1);
    }
    Node *temp = s->top;
    int val = temp->data;
    s->top = temp->next;
    free(temp);
    s->size--;
    return val;
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    return s->top->data;
}

void freeStack(Stack *s) {
    while (!isEmpty(s))
        pop(s);
}

int main(void) {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Size: %d\n", s.size);    /* 3 */
    printf("Top: %d\n", peek(&s));   /* 30 */
    printf("Pop: %d\n", pop(&s));    /* 30 */
    printf("Pop: %d\n", pop(&s));    /* 20 */

    freeStack(&s);
    return 0;
}

Size: 3
Top: 30
Pop: 30
Pop: 20

Key Points

•Push = insert at head, Pop = remove from head, both O(1)
•No fixed capacity -- grows and shrinks dynamically
•Each node requires extra memory for the next pointer
•Must free nodes on pop to avoid memory leaks
•Can track size with a counter for O(1) size queries

Gotchas

•Forgetting to free the popped node causes memory leaks
•malloc failure on push should be handled (check return value)
•More overhead per operation than array-based stack due to malloc/free
•Not cache-friendly -- nodes are scattered across heap

Push inserts at head, pop removes from head. Dynamic sizing with no capacity limit. All ops O(1) but has malloc/free overhead.

•Push at head, pop from head -- both O(1)
•No capacity limit

typedef struct Node { int data; struct Node *next; } Node;

void push(Node **top, int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = *top;
    *top = n;
}

int pop(Node **top) {
    Node *tmp = *top;
    int val = tmp->data;
    *top = tmp->next;
    free(tmp);
    return val;
}

Must free popped nodes to avoid memory leaks

Question 3 / 15

What are the core stack operations and how do push, pop, peek, and isEmpty work?

A stack is an abstract data type (ADT) with these core operations:

Operation	Description	Time
push(x)	Add element x to the top	O(1)
pop()	Remove and return the top element	O(1)
peek()/top()	Return the top element without removing	O(1)
isEmpty()	Return true if stack has no elements	O(1)
size()	Return number of elements	O(1)

LIFO principle: The last element added is the first removed. Think of a stack of plates.

Applications:

Function call stack (recursion)
Undo/redo functionality
Expression evaluation (postfix)
Parentheses matching
DFS traversal
Browser back button

Pseudo Code

Stack ADT operations:
  push(x)   -> adds x to top
  pop()     -> removes and returns top
  peek()    -> returns top without removal
  isEmpty() -> true if no elements
  size()    -> number of elements

All operations are O(1) time complexity.

Invariant: pop() returns elements in reverse order of push().

Code

#include <stdio.h>
#include <stdlib.h>

#define CAPACITY 10

typedef struct {
    int data[CAPACITY];
    int top;
} Stack;

void init(Stack *s)     { s->top = -1; }
int isEmpty(Stack *s)   { return s->top == -1; }
int isFull(Stack *s)    { return s->top == CAPACITY - 1; }
int size(Stack *s)      { return s->top + 1; }

void push(Stack *s, int val) {
    if (isFull(s)) { fprintf(stderr, "Overflow\n"); return; }
    s->data[++(s->top)] = val;
}

int pop(Stack *s) {
    if (isEmpty(s)) { fprintf(stderr, "Underflow\n"); return -1; }
    return s->data[(s->top)--];
}

int peek(Stack *s) {
    if (isEmpty(s)) { fprintf(stderr, "Empty\n"); return -1; }
    return s->data[s->top];
}

int main(void) {
    Stack s;
    init(&s);

    /* Demonstrate LIFO behavior */
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    printf("Size: %d\n", size(&s));    /* 3 */
    printf("Peek: %d\n", peek(&s));    /* 3 (not removed) */
    printf("Size: %d\n", size(&s));    /* 3 (unchanged) */

    while (!isEmpty(&s))
        printf("Pop: %d\n", pop(&s));  /* 3, 2, 1 (LIFO order) */

    printf("Empty: %d\n", isEmpty(&s));  /* 1 */
    return 0;
}

Size: 3
Peek: 3
Size: 3
Pop: 3
Pop: 2
Pop: 1
Empty: 1

Key Points

•All core operations (push, pop, peek, isEmpty) are O(1)
•LIFO: last in, first out -- pop returns elements in reverse push order
•peek() reads top without removal -- useful for lookahead
•Stack is an ADT -- can be implemented with array or linked list
•Function call stack in C uses a stack for activation records

Gotchas

•pop() on empty stack is undefined behavior if not checked -- always guard with isEmpty()
•peek() also needs an empty check -- same risk as pop()
•Returning -1 as error sentinel is ambiguous if -1 is valid data
•push() on a full array-based stack causes overflow if not checked

Stack ADT: push (add to top), pop (remove from top), peek (read top), isEmpty. All O(1). LIFO order. Implemented with array (fixed size) or linked list (dynamic).

•All operations O(1), LIFO order

void push(Stack *s, int v)  { s->data[++(s->top)] = v; }
int  pop(Stack *s)          { return s->data[(s->top)--]; }
int  peek(Stack *s)         { return s->data[s->top]; }
int  isEmpty(Stack *s)      { return s->top == -1; }

Always check isEmpty() before pop() or peek()

Question 4 / 15

How do you convert an infix expression to postfix using a stack?

The Shunting Yard algorithm (by Dijkstra) converts infix notation (e.g., A + B * C) to postfix/RPN (e.g., A B C * +) using a stack for operators.

Algorithm:

Scan tokens left to right
Operand: Output immediately
Operator: Pop operators with higher or equal precedence from stack to output, then push current operator
'(': Push onto stack
')': Pop to output until '(' is found, discard '('
After all tokens: pop remaining operators to output

Precedence: * / > + -. For left-associative operators, pop equal precedence too.

Example: A + B * C -> scan A (output), + (push), B (output), * (push, higher than +), C (output), end (pop * then +) -> A B C * +

Pseudo Code

InfixToPostfix(expression):
  for each token in expression:
    if token is operand:
      output(token)
    else if token is '(':
      stack.push(token)
    else if token is ')':
      while stack.top() != '(':
        output(stack.pop())
      stack.pop()  // discard '('
    else:  // operator
      while stack is not empty and
            stack.top() != '(' and
            precedence(stack.top()) >= precedence(token):
        output(stack.pop())
      stack.push(token)
  // Pop remaining operators
  while stack is not empty:
    output(stack.pop())

Code

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c)    { stack[++top] = c; }
char pop(void)       { return stack[top--]; }
char peek(void)      { return stack[top]; }
int isEmpty(void)    { return top == -1; }

int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '^': return 3;
        default: return 0;
    }
}

int isRightAssociative(char op) {
    return op == '^';
}

void infixToPostfix(const char *infix, char *postfix) {
    int j = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];

        if (isalnum(c)) {
            postfix[j++] = c;  /* operand -> output */
        } else if (c == '(') {
            push(c);
        } else if (c == ')') {
            while (!isEmpty() && peek() != '(')
                postfix[j++] = pop();
            pop();  /* discard '(' */
        } else {  /* operator */
            while (!isEmpty() && peek() != '(' &&
                   (precedence(peek()) > precedence(c) ||
                    (precedence(peek()) == precedence(c) && !isRightAssociative(c)))) {
                postfix[j++] = pop();
            }
            push(c);
        }
    }

    /* Pop remaining operators */
    while (!isEmpty())
        postfix[j++] = pop();

    postfix[j] = '\0';
}

int main(void) {
    char postfix[MAX];

    infixToPostfix("A+B*C", postfix);
    printf("A+B*C -> %s\n", postfix);       /* ABC*+ */

    infixToPostfix("(A+B)*C", postfix);
    printf("(A+B)*C -> %s\n", postfix);     /* AB+C* */

    infixToPostfix("A+B*C-D/E", postfix);
    printf("A+B*C-D/E -> %s\n", postfix);   /* ABC*+DE/- */

    infixToPostfix("A^B^C", postfix);
    printf("A^B^C -> %s\n", postfix);       /* ABC^^ (right-associative) */

    return 0;
}

A+B*C -> ABC*+
(A+B)*C -> AB+C*
A+B*C-D/E -> ABC*+DE/-
A^B^C -> ABC^^

Key Points

•Shunting Yard algorithm by Dijkstra
•Operands go directly to output, operators go on stack
•Pop higher/equal precedence operators before pushing
•Parentheses: '(' pushed, ')' pops until '(' found
•Right-associative operators (^) do not pop equal precedence

Gotchas

•Forgetting to handle right-associativity for ^ gives wrong result for A^B^C
•Not discarding the '(' when ')' is encountered leaves it in output
•Spaces in input need to be skipped if the expression has spaces
•Unmatched parentheses cause stack underflow or leftover '(' in output

Shunting Yard: operands go to output, operators go on stack. Pop higher/equal precedence ops before pushing. '(' pushes, ')' pops until '('. End: pop all remaining.

•Operands to output, operators to stack with precedence rules

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void infixToPostfix(const char *in, char *out) {
    char stack[100]; int top = -1, j = 0;
    for (int i = 0; in[i]; i++) {
        char c = in[i];
        if (isalnum(c)) out[j++] = c;
        else if (c == '(') stack[++top] = c;
        else if (c == ')') {
            while (stack[top] != '(') out[j++] = stack[top--];
            top--;  /* discard '(' */
        } else {
            while (top >= 0 && stack[top] != '(' &&
                   precedence(stack[top]) >= precedence(c))
                out[j++] = stack[top--];
            stack[++top] = c;
        }
    }
    while (top >= 0) out[j++] = stack[top--];
    out[j] = '\0';
}

Right-associative operators (^) need special handling

Question 5 / 15

How do you evaluate a postfix (RPN) expression using a stack?

Postfix (Reverse Polish Notation) evaluation is straightforward with a stack:

Scan tokens left to right
Operand: Push onto stack
Operator: Pop two operands, apply operator, push result
After all tokens, the stack contains the final result

Important: The first popped value is the right operand, the second is the left. This matters for non-commutative operators (-, /).

Example: 2 3 4 * + -> push 2, push 3, push 4, see : pop 4 and 3, compute 34=12, push 12, see +: pop 12 and 2, compute 2+12=14, push 14. Result: 14.

Pseudo Code

EvaluatePostfix(expression):
  for each token:
    if token is number:
      stack.push(token)
    else:  // operator
      right = stack.pop()
      left = stack.pop()
      result = apply(left, operator, right)
      stack.push(result)
  return stack.pop()  // final result

Code

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int val)  { stack[++top] = val; }
int pop(void)       { return stack[top--]; }

int evaluatePostfix(const char *expr) {
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];

        if (c == ' ') continue;  /* skip spaces */

        if (isdigit(c)) {
            push(c - '0');  /* convert char to int */
        } else {
            int right = pop();  /* first pop = right operand */
            int left = pop();   /* second pop = left operand */
            int result;

            switch (c) {
                case '+': result = left + right; break;
                case '-': result = left - right; break;
                case '*': result = left * right; break;
                case '/': 
                    if (right == 0) {
                        fprintf(stderr, "Division by zero\n");
                        exit(1);
                    }
                    result = left / right;
                    break;
                default:
                    fprintf(stderr, "Unknown operator: %c\n", c);
                    exit(1);
            }
            push(result);
        }
    }
    return pop();
}

int main(void) {
    printf("2 3 + = %d\n", evaluatePostfix("23+"));       /* 5 */
    printf("2 3 4 * + = %d\n", evaluatePostfix("234*+"));  /* 14 */
    printf("5 1 2 + 4 * + 3 - = %d\n",
           evaluatePostfix("512+4*+3-"));                    /* 14 */
    return 0;
}

2 3 + = 5
2 3 4 * + = 14
5 1 2 + 4 * + 3 - = 14

Key Points

•Operands pushed, operators pop two and push result
•First pop is right operand, second is left operand
•Order matters for - and /: left op right, not right op left
•Final result is the single value remaining on stack
•Postfix needs no parentheses -- precedence is implicit in order

Gotchas

•Swapping left/right operands gives wrong results for subtraction and division
•Division by zero must be checked
•Single-digit assumption: c - '0' only works for 0-9; multi-digit needs parsing
•If the expression is invalid (too few operands), stack underflow occurs

Scan left to right: push operands, for operators pop two (right first, then left), compute, push result. Final stack value is the answer.

•First pop = right operand, second = left

int evaluatePostfix(const char *expr) {
    int stack[100], top = -1;
    for (int i = 0; expr[i]; i++) {
        if (isdigit(expr[i])) {
            stack[++top] = expr[i] - '0';
        } else {
            int r = stack[top--], l = stack[top--];
            switch (expr[i]) {
                case '+': stack[++top] = l + r; break;
                case '-': stack[++top] = l - r; break;
                case '*': stack[++top] = l * r; break;
                case '/': stack[++top] = l / r; break;
            }
        }
    }
    return stack[top];
}

Swapping left/right gives wrong answer for - and /

Question 6 / 15

How do you check for balanced parentheses using a stack?

Balanced parentheses checking is a classic stack application. For each opening bracket, push it. For each closing bracket, pop and verify it matches.

Algorithm:

Scan string left to right
Opening bracket ((, [, {): Push onto stack
Closing bracket (), ], }): Pop from stack and check if it matches
At the end, the stack should be empty (all brackets matched)

Invalid cases:

Closing bracket with empty stack (extra closing)
Popped bracket does not match (mismatched types)
Non-empty stack at end (extra opening)

Pseudo Code

IsBalanced(str):
  for each char c in str:
    if c is opening bracket:
      stack.push(c)
    else if c is closing bracket:
      if stack is empty: return false
      top = stack.pop()
      if top does not match c: return false
  return stack.isEmpty()

Code

#include <stdio.h>
#include <string.h>

#define MAX 1000

char stack[MAX];
int top = -1;

void push(char c)  { stack[++top] = c; }
char pop(void)     { return stack[top--]; }
int isEmpty(void)  { return top == -1; }

int isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

int isBalanced(const char *expr) {
    top = -1;  /* reset stack */

    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];

        if (c == '(' || c == '[' || c == '{') {
            push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty())
                return 0;  /* extra closing bracket */
            char open = pop();
            if (!isMatchingPair(open, c))
                return 0;  /* mismatched brackets */
        }
        /* non-bracket characters are ignored */
    }

    return isEmpty();  /* true if all brackets matched */
}

int main(void) {
    const char *tests[] = {
        "{[()]}",       /* balanced */
        "{[(])}",       /* mismatched */
        "((())",        /* extra opening */
        "())",          /* extra closing */
        "a*(b+c)-[d/e]", /* balanced with non-bracket chars */
    };
    int n = sizeof(tests) / sizeof(tests[0]);

    for (int i = 0; i < n; i++) {
        printf("\"%s\" -> %s\n", tests[i],
               isBalanced(tests[i]) ? "Balanced" : "Not balanced");
    }
    /* Output:
       "{[()]}" -> Balanced
       "{[(])}" -> Not balanced
       "((())" -> Not balanced
       "())" -> Not balanced
       "a*(b+c)-[d/e]" -> Balanced
    */
    return 0;
}

Key Points

•Push opening brackets, pop and match on closing brackets
•Three failure conditions: empty stack on close, mismatch, non-empty at end
•Non-bracket characters should be ignored
•O(n) time, O(n) space in worst case (all opening brackets)
•Common interview question -- often the first stack application asked

Gotchas

•Forgetting to check isEmpty() before pop leads to stack underflow
•Only checking for '(' and ')' and forgetting '[' ']' '{' '}' in a full solution
•Not checking stack is empty at the end misses unmatched opening brackets
•Global stack state must be reset between calls (top = -1)

Push opening brackets. On closing, pop and check match. At end, stack must be empty. Three failure cases: empty stack on close, mismatch, non-empty at end.

•Push opens, pop and match on closes, stack must be empty at end

int isBalanced(const char *s) {
    char stack[1000]; int top = -1;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack[++top] = s[i];
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if (top < 0) return 0;
            char o = stack[top--];
            if ((s[i]==')' && o!='(') || (s[i]==']' && o!='[') || (s[i]=='}' && o!='{'))
                return 0;
        }
    }
    return top == -1;
}

Not checking empty stack at the end misses unmatched opening brackets

Question 7 / 15

How do you implement a queue using a circular array (circular buffer) in C?

A queue is a First-In-First-Out (FIFO) data structure. A circular buffer avoids the problem of wasted space in a linear array implementation.

Key idea: Use modulo arithmetic (% capacity) so indices wrap around from the end of the array back to the beginning.

Design:

front: index of the first element
rear: index of the last element (or next empty slot)
count: number of elements (simplifies full/empty detection)

Without count: Distinguish full from empty using (rear + 1) % capacity == front for full (wastes one slot) or use a boolean flag.

Operations: enqueue, dequeue, peek, isEmpty, isFull -- all O(1).

Pseudo Code

CircularQueue:
  arr[MAX], front = 0, rear = -1, count = 0

Enqueue(queue, value):
  if count == MAX: overflow
  rear = (rear + 1) % MAX
  arr[rear] = value
  count++

Dequeue(queue):
  if count == 0: underflow
  value = arr[front]
  front = (front + 1) % MAX
  count--
  return value

Code

#include <stdio.h>

#define MAX 5

typedef struct {
    int arr[MAX];
    int front;
    int rear;
    int count;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
    q->count = 0;
}

int isEmpty(Queue *q) { return q->count == 0; }
int isFull(Queue *q)  { return q->count == MAX; }

void enqueue(Queue *q, int val) {
    if (isFull(q)) {
        fprintf(stderr, "Queue overflow\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX;  /* wrap around */
    q->arr[q->rear] = val;
    q->count++;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        fprintf(stderr, "Queue underflow\n");
        return -1;
    }
    int val = q->arr[q->front];
    q->front = (q->front + 1) % MAX;  /* wrap around */
    q->count--;
    return val;
}

int peekFront(Queue *q) {
    if (isEmpty(q)) return -1;
    return q->arr[q->front];
}

int main(void) {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeue: %d\n", dequeue(&q));  /* 10 (FIFO) */

    enqueue(&q, 40);
    enqueue(&q, 50);
    /* Queue now wraps around in the array */
    enqueue(&q, 60);
    printf("Front: %d\n", peekFront(&q));  /* 20 */

    while (!isEmpty(&q))
        printf("Dequeue: %d\n", dequeue(&q));  /* 20, 30, 40, 50, 60 */

    return 0;
}

Dequeue: 10
Front: 20
Dequeue: 20
Dequeue: 30
Dequeue: 40
Dequeue: 50
Dequeue: 60

Key Points

•Circular buffer uses modulo to wrap indices: (index + 1) % MAX
•All operations are O(1)
•Using a count field simplifies full/empty detection
•FIFO: first enqueued element is first dequeued
•Without count, one slot is wasted to distinguish full from empty

Gotchas

•Without a count or flag, front == rear is ambiguous (full or empty)
•Forgetting the modulo wrap-around causes array out-of-bounds access
•Initializing rear to -1 (last occupied) vs front (next empty) changes the logic
•Fixed capacity -- must either reject or resize on overflow

Circular array queue: use % capacity for index wrap-around. Track front, rear, and count. FIFO: enqueue at rear, dequeue from front. All ops O(1).

•Modulo arithmetic for circular wrap-around, all ops O(1)

typedef struct { int arr[100]; int front, rear, count; } Queue;

void initQueue(Queue *q) { q->front = 0; q->rear = -1; q->count = 0; }
void enqueue(Queue *q, int v) {
    q->rear = (q->rear + 1) % 100;
    q->arr[q->rear] = v;
    q->count++;
}
int dequeue(Queue *q) {
    int v = q->arr[q->front];
    q->front = (q->front + 1) % 100;
    q->count--;
    return v;
}

Without count field, full and empty states look the same (front == rear)

Question 8 / 15

How do you implement a queue using a linked list in C?

A linked-list queue maintains front and rear pointers:

Enqueue: Create a new node, attach to rear, update rear pointer
Dequeue: Remove the front node, update front pointer

Both operations are O(1) because we maintain a tail/rear pointer.

Advantages: No fixed capacity, grows dynamically. Disadvantages: malloc/free overhead per operation, not cache-friendly.

Empty queue: Both front and rear are NULL.

Pseudo Code

Queue:
  Node *front = NULL
  Node *rear = NULL

Enqueue(queue, value):
  new = createNode(value)
  if rear is NULL:
    front = rear = new
  else:
    rear->next = new
    rear = new

Dequeue(queue):
  if front is NULL: underflow
  temp = front
  value = temp->data
  front = front->next
  if front is NULL: rear = NULL
  free(temp)
  return value

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
    int count;
} Queue;

void initQueue(Queue *q) {
    q->front = q->rear = NULL;
    q->count = 0;
}

int isEmpty(Queue *q) { return q->front == NULL; }

void enqueue(Queue *q, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) { perror("malloc"); exit(1); }
    newNode->data = val;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->count++;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        fprintf(stderr, "Queue underflow\n");
        return -1;
    }
    Node *temp = q->front;
    int val = temp->data;
    q->front = q->front->next;

    if (q->front == NULL)
        q->rear = NULL;  /* queue is now empty */

    free(temp);
    q->count--;
    return val;
}

int peekFront(Queue *q) {
    if (isEmpty(q)) return -1;
    return q->front->data;
}

void freeQueue(Queue *q) {
    while (!isEmpty(q))
        dequeue(q);
}

int main(void) {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Front: %d\n", peekFront(&q));    /* 10 */
    printf("Dequeue: %d\n", dequeue(&q));    /* 10 */
    printf("Dequeue: %d\n", dequeue(&q));    /* 20 */
    printf("Count: %d\n", q.count);          /* 1 */

    freeQueue(&q);
    return 0;
}

Front: 10
Dequeue: 10
Dequeue: 20
Count: 1

Key Points

•Maintain both front and rear pointers for O(1) enqueue and dequeue
•Enqueue at rear, dequeue from front (FIFO)
•When dequeuing the last element, must set rear to NULL too
•No fixed capacity -- grows dynamically
•Free nodes on dequeue to prevent memory leaks

Gotchas

•Forgetting to update rear to NULL when the last element is dequeued causes dangling pointer
•Enqueue on empty queue: must set both front AND rear to the new node
•malloc failure on enqueue should be handled
•More memory per element than array queue (pointer overhead)

Maintain front and rear pointers. Enqueue at rear, dequeue from front. Both O(1). When last element removed, set both to NULL.

•Front and rear pointers, both O(1)

typedef struct Node { int data; struct Node *next; } Node;
typedef struct { Node *front; Node *rear; } Queue;

void enqueue(Queue *q, int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val; n->next = NULL;
    if (!q->rear) { q->front = q->rear = n; return; }
    q->rear->next = n; q->rear = n;
}

int dequeue(Queue *q) {
    Node *tmp = q->front;
    int val = tmp->data;
    q->front = tmp->next;
    if (!q->front) q->rear = NULL;
    free(tmp);
    return val;
}

Must NULL rear when dequeuing the last element

Question 9 / 15

How do you define a binary tree node and implement basic tree structure in C?

A binary tree node contains data and pointers to left and right children. Each node has at most two children.

Terminology:

Root: Top node with no parent
Leaf: Node with no children (both left and right are NULL)
Height: Longest path from root to a leaf
Depth: Distance from root to a node
Complete binary tree: All levels filled except possibly the last (filled left to right)
Full binary tree: Every node has 0 or 2 children
Perfect binary tree: All interior nodes have 2 children, all leaves at same level

A tree with n nodes has exactly n-1 edges.

Pseudo Code

TreeNode structure:
  int data
  TreeNode *left
  TreeNode *right

CreateNode(value):
  node = malloc(sizeof(TreeNode))
  node->data = value
  node->left = NULL
  node->right = NULL
  return node

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    if (!node) { perror("malloc"); exit(1); }
    node->data = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* Check if a node is a leaf */
int isLeaf(TreeNode *node) {
    return node != NULL && node->left == NULL && node->right == NULL;
}

/* Count total nodes */
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

/* Count leaf nodes */
int countLeaves(TreeNode *root) {
    if (root == NULL) return 0;
    if (isLeaf(root)) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

void freeTree(TreeNode *root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main(void) {
    /*       1
     *      / \
     *     2   3
     *    / \
     *   4   5
     */
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Total nodes: %d\n", countNodes(root));   /* 5 */
    printf("Leaf nodes: %d\n", countLeaves(root));   /* 3 (nodes 3, 4, 5) */
    printf("Is 3 a leaf? %d\n", isLeaf(root->right)); /* 1 */
    printf("Is 2 a leaf? %d\n", isLeaf(root->left));  /* 0 */

    freeTree(root);
    return 0;
}

Total nodes: 5
Leaf nodes: 3
Is 3 a leaf? 1
Is 2 a leaf? 0

Key Points

•Binary tree node: data + left pointer + right pointer
•Leaf node: both children are NULL
•Tree with n nodes has n-1 edges
•Recursive structure: trees are naturally recursive (subtrees)
•Always free tree with post-order traversal (free children before parent)

Gotchas

•Forgetting to initialize left and right to NULL leads to garbage pointers
•Freeing a tree requires post-order (children first) -- freeing parent first loses child pointers
•Binary tree is NOT the same as binary search tree (BST has ordering)
•A tree with only one node has height 0 (or 1, depending on convention -- clarify with interviewer)

Binary tree node has data, left child, and right child pointers. Leaf = both children NULL. Recursion is natural for tree operations.

•Data + left + right pointers
•Initialize children to NULL

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

Not initializing children to NULL leads to garbage pointers

Question 10 / 15

How do you implement inorder, preorder, and postorder tree traversals recursively?

The three depth-first tree traversals differ only in when the root is processed relative to its children:

Traversal	Order	Use Case
Inorder	Left, Root, Right	BST gives sorted order
Preorder	Root, Left, Right	Copy tree, serialize
Postorder	Left, Right, Root	Delete tree, evaluate expression tree

All three are O(n) time and O(h) space (call stack), where h is the height.

Mnemonic: The name tells you when the root is visited:

Inorder: root is in the middle
Preorder: root is before (first)
Postorder: root is after (last)

Pseudo Code

Inorder(node):
  if node is NULL: return
  Inorder(node->left)     // L
  process(node->data)     // Root
  Inorder(node->right)    // R

Preorder(node):
  if node is NULL: return
  process(node->data)     // Root
  Preorder(node->left)    // L
  Preorder(node->right)   // R

Postorder(node):
  if node is NULL: return
  Postorder(node->left)   // L
  Postorder(node->right)  // R
  process(node->data)     // Root

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

/* Inorder: Left, Root, Right */
void inorder(TreeNode *node) {
    if (node == NULL) return;
    inorder(node->left);
    printf("%d ", node->data);
    inorder(node->right);
}

/* Preorder: Root, Left, Right */
void preorder(TreeNode *node) {
    if (node == NULL) return;
    printf("%d ", node->data);
    preorder(node->left);
    preorder(node->right);
}

/* Postorder: Left, Right, Root */
void postorder(TreeNode *node) {
    if (node == NULL) return;
    postorder(node->left);
    postorder(node->right);
    printf("%d ", node->data);
}

int main(void) {
    /*       1
     *      / \
     *     2   3
     *    / \
     *   4   5
     */
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder:   "); inorder(root);   printf("\n");  /* 4 2 5 1 3 */
    printf("Preorder:  "); preorder(root);  printf("\n");  /* 1 2 4 5 3 */
    printf("Postorder: "); postorder(root); printf("\n");  /* 4 5 2 3 1 */

    return 0;
}

Inorder:   4 2 5 1 3 
Preorder:  1 2 4 5 3 
Postorder: 4 5 2 3 1

Key Points

•Inorder (L-Root-R): gives sorted order for BST
•Preorder (Root-L-R): used to copy/serialize a tree
•Postorder (L-R-Root): used to free/delete a tree
•All are O(n) time, O(h) space where h = height
•Base case is always: if node == NULL, return

Gotchas

•Inorder on a non-BST tree does NOT produce sorted output
•Deep/skewed trees cause stack overflow with recursive traversals
•Forgetting the NULL base case causes segfault
•For tree deletion, MUST use postorder (free children before parent)

Inorder: L, Root, R (sorted for BST). Preorder: Root, L, R (copy/serialize). Postorder: L, R, Root (delete/free). All O(n) time, O(h) space.

•Name tells when root is visited: pre (first), in (middle), post (last)

void inorder(TreeNode *n) {
    if (!n) return;
    inorder(n->left);
    printf("%d ", n->data);
    inorder(n->right);
}
void preorder(TreeNode *n) {
    if (!n) return;
    printf("%d ", n->data);
    preorder(n->left);
    preorder(n->right);
}
void postorder(TreeNode *n) {
    if (!n) return;
    postorder(n->left);
    postorder(n->right);
    printf("%d ", n->data);
}

Use postorder to free a tree -- freeing parent first loses children

Question 11 / 15

How do you implement level-order (BFS) traversal of a binary tree using a queue?

Level-order traversal visits nodes level by level, left to right. It uses a queue (FIFO) instead of the call stack.

Algorithm:

Enqueue the root
While queue is not empty: a. Dequeue a node, process it b. Enqueue its left child (if exists) c. Enqueue its right child (if exists)

This is essentially BFS (Breadth-First Search) on a tree.

Time: O(n), Space: O(w) where w is the maximum width of the tree (up to n/2 for a complete tree).

Variant: To print level by level (with newlines), track the size of the queue at the start of each level.

Pseudo Code

LevelOrder(root):
  if root is NULL: return
  queue = empty queue
  enqueue(root)
  while queue is not empty:
    node = dequeue()
    process(node->data)
    if node->left: enqueue(node->left)
    if node->right: enqueue(node->right)

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

/* Simple queue for tree node pointers */
#define MAX_Q 100
typedef struct {
    TreeNode *arr[MAX_Q];
    int front, rear, count;
} Queue;

void initQ(Queue *q) { q->front = 0; q->rear = -1; q->count = 0; }
int isEmptyQ(Queue *q) { return q->count == 0; }
void enqueue(Queue *q, TreeNode *node) {
    q->rear = (q->rear + 1) % MAX_Q;
    q->arr[q->rear] = node;
    q->count++;
}
TreeNode *dequeue(Queue *q) {
    TreeNode *node = q->arr[q->front];
    q->front = (q->front + 1) % MAX_Q;
    q->count--;
    return node;
}

/* Level-order (BFS) traversal */
void levelOrder(TreeNode *root) {
    if (root == NULL) return;

    Queue q;
    initQ(&q);
    enqueue(&q, root);

    while (!isEmptyQ(&q)) {
        TreeNode *node = dequeue(&q);
        printf("%d ", node->data);

        if (node->left)  enqueue(&q, node->left);
        if (node->right) enqueue(&q, node->right);
    }
    printf("\n");
}

/* Level-by-level printing */
void levelOrderByLevel(TreeNode *root) {
    if (root == NULL) return;

    Queue q;
    initQ(&q);
    enqueue(&q, root);

    while (!isEmptyQ(&q)) {
        int levelSize = q.count;  /* nodes at current level */
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = dequeue(&q);
            printf("%d ", node->data);
            if (node->left)  enqueue(&q, node->left);
            if (node->right) enqueue(&q, node->right);
        }
        printf("\n");  /* newline after each level */
    }
}

int main(void) {
    /*       1
     *      / \
     *     2   3
     *    / \   \
     *   4   5   6
     */
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);

    printf("Level order: ");
    levelOrder(root);          /* 1 2 3 4 5 6 */

    printf("By level:\n");
    levelOrderByLevel(root);
    /* 1
       2 3
       4 5 6 */

    return 0;
}

Level order: 1 2 3 4 5 6 
By level:
1 
2 3 
4 5 6

Key Points

•BFS using a queue: enqueue root, dequeue-process-enqueue children
•O(n) time, O(w) space where w = max width
•Level-by-level: track queue size at start of each level
•Unlike DFS traversals (inorder etc.), this is not naturally recursive
•C has no built-in queue -- must implement one (array or linked list)

Gotchas

•Queue must store pointers (TreeNode *), not copies of nodes
•Queue overflow if tree is too wide for the array -- size accordingly
•NULL root should be handled before enqueuing
•This is BFS, not DFS -- uses queue, not stack

BFS with a queue: enqueue root, then repeatedly dequeue, process, enqueue children. O(n) time, O(w) space.

•Queue-based BFS: enqueue root, dequeue-process-enqueue children

void levelOrder(TreeNode *root) {
    if (!root) return;
    TreeNode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode *n = queue[front++];
        printf("%d ", n->data);
        if (n->left)  queue[rear++] = n->left;
        if (n->right) queue[rear++] = n->right;
    }
}

Linear queue (non-circular) wastes space -- use circular for production

Question 12 / 15

How do you implement insert, search, and delete operations in a Binary Search Tree (BST)?

A Binary Search Tree (BST) maintains the invariant: for every node, all values in the left subtree are less and all values in the right subtree are greater.

Search (O(h)): Compare target with current node. Go left if smaller, right if larger.

Insert (O(h)): Search for the correct position, insert as a leaf.

Delete (O(h)): Three cases:

Leaf node: Simply remove (free)
One child: Replace node with its child
Two children: Replace with inorder successor (smallest in right subtree) or inorder predecessor (largest in left subtree), then delete the successor

h is the height: O(log n) for balanced trees, O(n) for skewed trees.

Pseudo Code

Search(root, key):
  if root is NULL or root->data == key: return root
  if key < root->data: return Search(root->left, key)
  else: return Search(root->right, key)

Insert(root, key):
  if root is NULL: return createNode(key)
  if key < root->data: root->left = Insert(root->left, key)
  else if key > root->data: root->right = Insert(root->right, key)
  return root  // duplicate ignored

Delete(root, key):
  if root is NULL: return NULL
  if key < root->data: root->left = Delete(root->left, key)
  else if key > root->data: root->right = Delete(root->right, key)
  else:  // found the node
    if no left child: return right child
    if no right child: return left child
    // two children: find inorder successor
    successor = minNode(root->right)
    root->data = successor->data
    root->right = Delete(root->right, successor->data)

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

/* Search: O(h) */
TreeNode *search(TreeNode *root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}

/* Insert: O(h) */
TreeNode *insert(TreeNode *root, int key) {
    if (root == NULL)
        return createNode(key);
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    /* duplicate keys ignored */
    return root;
}

/* Find minimum node in a subtree */
TreeNode *findMin(TreeNode *node) {
    while (node->left != NULL)
        node = node->left;
    return node;
}

/* Delete: O(h) */
TreeNode *delete(TreeNode *root, int key) {
    if (root == NULL) return NULL;

    if (key < root->data) {
        root->left = delete(root->left, key);
    } else if (key > root->data) {
        root->right = delete(root->right, key);
    } else {
        /* Found the node to delete */

        /* Case 1 & 2: zero or one child */
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        }
        if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }

        /* Case 3: two children */
        TreeNode *successor = findMin(root->right);
        root->data = successor->data;
        root->right = delete(root->right, successor->data);
    }
    return root;
}

void inorder(TreeNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main(void) {
    TreeNode *root = NULL;
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++)
        root = insert(root, keys[i]);

    printf("Inorder: "); inorder(root); printf("\n");
    /* 20 30 40 50 60 70 80 */

    /* Search */
    TreeNode *found = search(root, 40);
    printf("Found 40: %s\n", found ? "yes" : "no");  /* yes */

    /* Delete node with two children (50) */
    root = delete(root, 50);
    printf("After deleting 50: "); inorder(root); printf("\n");
    /* 20 30 40 60 70 80 */

    return 0;
}

Inorder: 20 30 40 50 60 70 80 
Found 40: yes
After deleting 50: 20 30 40 60 70 80

Key Points

•BST invariant: left < root < right
•Search, insert, delete are all O(h) where h is the height
•Delete with two children: replace with inorder successor (min of right subtree)
•Inorder traversal of BST gives sorted order
•Balanced BST: h = O(log n), skewed BST: h = O(n)

Gotchas

•delete is a keyword-like identifier in C++ but valid in C -- still, consider naming it bstDelete
•Forgetting to reassign root->left or root->right from the recursive call loses the updated subtree
•Deleting a node and not freeing it causes memory leak
•Duplicate handling must be defined: ignore, count, or store in left/right

BST: left < root < right. Search/insert follow comparisons. Delete has 3 cases: leaf, one child (replace with child), two children (replace with inorder successor). All O(h).

•Left < root < right, all ops O(h)

TreeNode *insert(TreeNode *root, int key) {
    if (!root) return createNode(key);
    if (key < root->data) root->left = insert(root->left, key);
    else if (key > root->data) root->right = insert(root->right, key);
    return root;
}

TreeNode *search(TreeNode *root, int key) {
    if (!root || root->data == key) return root;
    return key < root->data ? search(root->left, key) : search(root->right, key);
}

Skewed BST degrades to O(n) -- use balanced BST (AVL/Red-Black) for guarantee

Question 13 / 15

How do you find the height (or depth) of a binary tree?

Height of a tree is the number of edges on the longest path from the root to a leaf. (Some definitions count nodes instead of edges -- clarify with interviewer.)

Recursive approach:

Height of NULL tree = -1 (edge convention) or 0 (node convention)
Height = 1 + max(height(left), height(right))

Iterative approach: Use level-order traversal and count levels.

Common conventions:

Empty tree: height = -1 (edge-based) or 0 (some use this)
Single node: height = 0 (edge-based) or 1 (node-based)

Time: O(n), Space: O(h) for recursive, O(w) for iterative.

Pseudo Code

Height(root):
  if root is NULL:
    return -1  // edge convention
  leftHeight = Height(root->left)
  rightHeight = Height(root->right)
  return 1 + max(leftHeight, rightHeight)

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

/* Height: number of edges on longest root-to-leaf path */
int height(TreeNode *root) {
    if (root == NULL)
        return -1;  /* edge convention: empty tree has height -1 */

    int leftH = height(root->left);
    int rightH = height(root->right);

    return 1 + (leftH > rightH ? leftH : rightH);
}

/* Alternative: node-count convention (height = number of nodes on longest path) */
int heightNodeCount(TreeNode *root) {
    if (root == NULL)
        return 0;

    int leftH = heightNodeCount(root->left);
    int rightH = heightNodeCount(root->right);

    return 1 + (leftH > rightH ? leftH : rightH);
}

/* Depth of a specific node (distance from root) */
int depth(TreeNode *root, int target, int currentDepth) {
    if (root == NULL) return -1;
    if (root->data == target) return currentDepth;

    int left = depth(root->left, target, currentDepth + 1);
    if (left != -1) return left;
    return depth(root->right, target, currentDepth + 1);
}

int main(void) {
    /*       1
     *      / \
     *     2   3
     *    /
     *   4
     *  /
     * 5
     */
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->left->left = createNode(5);

    printf("Height (edges): %d\n", height(root));           /* 3 */
    printf("Height (nodes): %d\n", heightNodeCount(root));  /* 4 */
    printf("Depth of 4: %d\n", depth(root, 4, 0));          /* 2 */
    printf("Depth of 5: %d\n", depth(root, 5, 0));          /* 3 */

    return 0;
}

Height (edges): 3
Height (nodes): 4
Depth of 4: 2
Depth of 5: 3

Key Points

•Height = 1 + max(left height, right height)
•Base case: NULL returns -1 (edge convention) or 0 (node convention)
•Depth of a node = distance from root (0 for root)
•O(n) time -- must visit every node
•Height of balanced tree: O(log n), skewed tree: O(n)

Gotchas

•Convention ambiguity: edge-count vs node-count -- clarify with interviewer
•Empty tree height: -1 or 0 depending on convention
•Height and depth are different: height goes down (root to leaf), depth goes down (root to node)
•C has no built-in max() -- use ternary operator or define a macro

Recursively: height(node) = 1 + max(height(left), height(right)). Base: NULL returns -1 (edge count) or 0 (node count). O(n) time.

•height = 1 + max(left, right), base = -1 for NULL

int height(TreeNode *root) {
    if (!root) return -1;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

Clarify edge-count vs node-count convention with interviewer

Question 14 / 15

How do you check if a binary tree is a valid BST?

Checking if a tree is a valid BST requires verifying that every node satisfies the BST property, not just its immediate children.

Wrong approach: Checking node->left->data < node->data < node->right->data only checks direct children. A node deep in the left subtree could still violate the BST property relative to an ancestor.

Correct approach 1 -- Min/Max range: Pass valid range (min, max) down the recursion. Each node must be within its allowed range.

Correct approach 2 -- Inorder traversal: Inorder traversal of a BST produces sorted output. Track the previous value and ensure each value is greater.

Time: O(n), Space: O(h) for both approaches.

Pseudo Code

Approach 1 - Range check:
IsBST(node, min, max):
  if node is NULL: return true
  if node->data <= min or node->data >= max: return false
  return IsBST(node->left, min, node->data) AND
         IsBST(node->right, node->data, max)

Initial call: IsBST(root, INT_MIN, INT_MAX)

Approach 2 - Inorder:
IsBST_Inorder(node, prev):
  if node is NULL: return true
  if !IsBST_Inorder(node->left, prev): return false
  if *prev >= node->data: return false
  *prev = node->data
  return IsBST_Inorder(node->right, prev)

Code

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

/* Approach 1: Min/Max range check */
int isBSTHelper(TreeNode *node, long min, long max) {
    if (node == NULL) return 1;

    if (node->data <= min || node->data >= max)
        return 0;

    return isBSTHelper(node->left, min, node->data) &&
           isBSTHelper(node->right, node->data, max);
}

int isBST(TreeNode *root) {
    return isBSTHelper(root, LONG_MIN, LONG_MAX);
}

/* Approach 2: Inorder traversal check */
int isBSTInorder(TreeNode *node, long *prev) {
    if (node == NULL) return 1;

    if (!isBSTInorder(node->left, prev))
        return 0;

    if (*prev >= node->data)
        return 0;  /* not strictly increasing */

    *prev = node->data;
    return isBSTInorder(node->right, prev);
}

int isBSTv2(TreeNode *root) {
    long prev = LONG_MIN;
    return isBSTInorder(root, &prev);
}

int main(void) {
    /* Valid BST:
     *       5
     *      / \
     *     3   7
     *    / \   \
     *   2   4   8
     */
    TreeNode *valid = createNode(5);
    valid->left = createNode(3);
    valid->right = createNode(7);
    valid->left->left = createNode(2);
    valid->left->right = createNode(4);
    valid->right->right = createNode(8);

    /* Invalid BST (6 in left subtree > 5):
     *       5
     *      / \
     *     3   7
     *      \
     *       6    <-- violates BST: 6 > 5 but in left subtree
     */
    TreeNode *invalid = createNode(5);
    invalid->left = createNode(3);
    invalid->right = createNode(7);
    invalid->left->right = createNode(6);

    printf("Valid tree is BST: %d\n", isBST(valid));      /* 1 */
    printf("Invalid tree is BST: %d\n", isBST(invalid));  /* 0 */
    printf("Valid (v2): %d\n", isBSTv2(valid));            /* 1 */
    printf("Invalid (v2): %d\n", isBSTv2(invalid));        /* 0 */

    return 0;
}

Valid tree is BST: 1
Invalid tree is BST: 0
Valid (v2): 1
Invalid (v2): 0

Key Points

•Must check against ALL ancestors, not just parent
•Range approach: pass (min, max) bounds down recursion
•Inorder approach: values must be strictly increasing
•Use long for bounds to handle INT_MIN/INT_MAX edge cases
•O(n) time, O(h) space for both approaches

Gotchas

•Checking only immediate children is WRONG -- must validate against full ancestor chain
•Using int for bounds fails when node values are INT_MIN or INT_MAX -- use long
•Equal values: decide if duplicates are allowed (usually not in a BST)
•Inorder approach must use a pointer for prev to maintain state across recursive calls

Pass (min, max) range down recursion. Each node must be within range. Or: inorder traversal must be strictly increasing. Both O(n).

•Range check validates against ALL ancestors, not just parent

int isBSTHelper(TreeNode *n, long min, long max) {
    if (!n) return 1;
    if (n->data <= min || n->data >= max) return 0;
    return isBSTHelper(n->left, min, n->data) &&
           isBSTHelper(n->right, n->data, max);
}
int isBST(TreeNode *root) {
    return isBSTHelper(root, LONG_MIN, LONG_MAX);
}

Checking only direct children is wrong -- will miss violations deeper in the tree

Question 15 / 15

How do you find the minimum and maximum values in a BST?

In a BST, the minimum value is at the leftmost node and the maximum is at the rightmost node.

Minimum: Keep going left until node->left == NULL. Maximum: Keep going right until node->right == NULL.

Time: O(h) where h is the height (O(log n) for balanced BST, O(n) for skewed).

This property is used in:

BST deletion (finding inorder successor = min of right subtree)
Range queries
Floor/ceiling operations

Recursive vs Iterative: Both are straightforward, but iterative is preferred (no stack overhead).

Pseudo Code

FindMin(root):
  if root is NULL: error (empty tree)
  while root->left != NULL:
    root = root->left
  return root

FindMax(root):
  if root is NULL: error (empty tree)
  while root->right != NULL:
    root = root->right
  return root

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int val) {
    TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

TreeNode *insert(TreeNode *root, int key) {
    if (!root) return createNode(key);
    if (key < root->data) root->left = insert(root->left, key);
    else if (key > root->data) root->right = insert(root->right, key);
    return root;
}

/* Iterative: find minimum (leftmost node) */
TreeNode *findMin(TreeNode *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

/* Iterative: find maximum (rightmost node) */
TreeNode *findMax(TreeNode *root) {
    if (root == NULL) return NULL;
    while (root->right != NULL)
        root = root->right;
    return root;
}

/* Recursive versions */
TreeNode *findMinRecursive(TreeNode *root) {
    if (root == NULL || root->left == NULL)
        return root;
    return findMinRecursive(root->left);
}

TreeNode *findMaxRecursive(TreeNode *root) {
    if (root == NULL || root->right == NULL)
        return root;
    return findMaxRecursive(root->right);
}

int main(void) {
    TreeNode *root = NULL;
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 10};
    for (int i = 0; i < 8; i++)
        root = insert(root, keys[i]);

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

    TreeNode *minNode = findMin(root);
    TreeNode *maxNode = findMax(root);

    printf("Minimum: %d\n", minNode->data);  /* 10 */
    printf("Maximum: %d\n", maxNode->data);  /* 80 */

    /* Min/max of a subtree (used in BST delete) */
    TreeNode *minRight = findMin(root->right);
    printf("Min of right subtree: %d\n", minRight->data);  /* 60 */

    return 0;
}

Minimum: 10
Maximum: 80
Min of right subtree: 60

Key Points

•Minimum: leftmost node (keep going left)
•Maximum: rightmost node (keep going right)
•O(h) time where h = tree height
•Finding min of right subtree gives inorder successor (used in BST delete)
•Iterative preferred over recursive (no stack overhead)

Gotchas

•Calling findMin/findMax on an empty tree (NULL root) -- must handle this case
•This only works for BSTs, not general binary trees
•For a general binary tree, you must traverse ALL nodes: O(n)
•Skewed BST (all left or all right) degrades to O(n)

Min: follow left pointers to the leftmost node. Max: follow right pointers to the rightmost. O(h) time. Only works for BSTs.

•Min = leftmost, Max = rightmost, O(h)

TreeNode *findMin(TreeNode *root) {
    while (root && root->left) root = root->left;
    return root;
}
TreeNode *findMax(TreeNode *root) {
    while (root && root->right) root = root->right;
    return root;
}

Only works for BSTs -- general binary trees need full traversal

Built by onllm.dev

Home GitHub Support awesomePrep