Source: COP 3502C Coding Problems (Stacks & Queues)
Tags: preorder traversal, level-order traversal, BFS, binary tree, iterative traversal, stack traversal, queue traversal, expression validation, operator precedence, COP 3502C, Computer Science I, UCF, C programming
Difficulty: Intermediate to Advanced Prerequisites: You should be comfortable with stack and queue implementations in C (see Part 1) and have a basic understanding of binary tree structures (nodes with left/right child pointers). Familiarity with operator precedence from Part 2 is also helpful.
Tree traversals and expression validation bring together everything from the earlier stack and queue material. A preorder traversal of a binary tree uses a stack in the same push/pop pattern you already know, just with tree-node pointers instead of integers. A level-order traversal (breadth-first search) uses a queue. Expression validation combines balanced-parentheses checking with operator-precedence rules. These three problems round out the exam-relevant applications of stacks and queues in COP 3502C.
Preorder traversal uses a stack to visit root-left-right iteratively. Level-order traversal uses a queue to visit nodes one level at a time. Expression validation uses a stack to check both bracket balance and operator precedence simultaneously.
Binary tree
A tree data structure where each node has at most two children, referred to as the left child and the right child. Think of it as a family tree that branches into exactly two lines at every generation.
Preorder traversal
A tree traversal that visits the current node first, then recursively visits the left subtree, then the right subtree. The order is: root, left, right.
Level-order traversal (breadth-first search, BFS)
A tree traversal that visits all nodes at depth 0, then all at depth 1, then depth 2, and so on. It processes the tree one horizontal layer at a time.
Iterative traversal
Performing a tree traversal using an explicit stack or queue rather than recursion. Useful when you want to avoid the overhead (or risk of stack overflow) of recursive calls.
Expression validation
Checking whether an arithmetic expression is well-formed: balanced parentheses, correct operator placement, and no precedence violations.
The recursive version of preorder is short: visit node, recurse left, recurse right. The iterative version replaces the call stack with an explicit stack of node pointers.
Algorithm:
Push the root node onto the stack.
While the stack is not empty: pop the top node, process it (e.g. print its data), then push its right child first, then its left child.
Pushing right before left ensures that left is processed first (since the stack is LIFO).
Key structures (the stack stores node pointers, not integers):
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
typedef struct stack {
node *n;
struct stack *next;
} stack;
This is a linked-list-based stack of tree-node pointers. The push and pop functions use a double pointer (stack **s) so they can modify the head of the linked list.
void preorder(node *root) {
stack *s = NULL;
push(&s, root);
while (!is_empty(s)) {
node *current = pop(&s);
printf("%d ", current->data);
if (current->right != NULL)
push(&s, current->right);
if (current->left != NULL)
push(&s, current->left);
}
}
The right child is pushed before the left child. This is the critical detail that makes the traversal come out in the correct root-left-right order.
Level-order traversal is breadth-first search applied to a tree. It uses a queue rather than a stack, which means nodes are visited in the order they were discovered, layer by layer.
Algorithm:
Enqueue the root node.
While the queue is not empty: dequeue the front node, process it, then enqueue its left child (if it exists), then its right child (if it exists).
void level_order(node *root) {
queue *q = NULL;
enqueue(&q, root);
while (!is_empty(q)) {
node *n = dequeue(&q);
printf("%d ", n->data);
if (n->left != NULL)
enqueue(&q, n->left);
if (n->right != NULL)
enqueue(&q, n->right);
}
}
Because FIFO ordering processes things in the order they arrived, and children at depth d are enqueued before any children at depth d+1, the output naturally comes out level by level.
Property | Preorder (Stack) | Level-Order (Queue) |
|---|---|---|
Data structure | Stack (LIFO) | Queue (FIFO) |
Visit order | Root, left subtree, right subtree | Level by level, left to right |
Child push order | Right first, then left | Left first, then right |
Typical use case | Copying a tree, prefix expression | Finding shortest path, printing by level |
The "child push order" row is where students often slip up. For the stack, you push right first so that left gets popped first. For the queue, you enqueue left first because FIFO preserves insertion order.
This problem combines balanced-parentheses checking with operator-precedence checking. The function is_valid_expression does two things as it scans the string:
Tracks bracket balance using the same push/pop pattern from Part 2.
Checks that each new operator has strictly higher precedence than the operator currently on top of the stack. If a new operator's precedence is less than or equal to the top, the expression is considered invalid (under the rules given in this problem set).
bool is_valid_expression(char *str) {
stack s;
s.top = -1;
int len = strlen(str);
for (int i = 0; i < len; i++) {
char c = str[i];
if (c >= '0' && c <= '9') continue;
if (c == '(') {
push(&s, c);
} else if (c == ')') {
if (s.top == -1 || pop(&s) != '(')
return false;
} else {
if (s.top != -1 &&
precedence(c) <= precedence(s.data[s.top]))
return false;
push(&s, c);
}
}
return s.top == -1;
}
The precedence function is the same one from the infix-to-postfix section: * and / return 2, + and - return 1, everything else returns 0.
A few things to note about this specific implementation:
Digits are skipped entirely (they are valid but need no stack interaction).
Opening parentheses are pushed. Closing parentheses trigger a pop-and-match.
Operators are pushed only if their precedence is strictly greater than whatever is on top. Otherwise the expression is rejected.
The final s.top == -1 check catches unmatched opening parentheses.
Preorder traversal order: Root → Left → Right
Level-order traversal order: Depth 0 → Depth 1 → Depth 2 → ...
Example tree:
1
/ \
2 3
/ \
4 5
Preorder: 1, 2, 4, 5, 3
Level-order: 1, 2, 3, 4, 5
Level-order traversal is the foundation of breadth-first search, which is used in network routing, social graph analysis (finding degrees of separation), and shortest-path algorithms on unweighted graphs. Preorder traversal is used when serialising a tree structure to disk or transmitting it over a network, because the root-first order makes it straightforward to reconstruct. Expression validation is a simplified version of what parsers in compilers and interpreters do when checking whether source code is syntactically correct.
Students often push children in the wrong order for preorder traversal. If you push left before right, left ends up deeper in the stack and gets processed second, giving you root-right-left instead of root-left-right.
Students confuse level-order traversal with inorder traversal. Inorder (left-root-right) is a depth-first traversal and uses a stack (or recursion). Level-order is breadth-first and uses a queue. They produce very different outputs.
In expression validation, students sometimes assume that any expression with balanced parentheses is valid. The precedence check adds a second layer: (1 + 2 * 3 fails the bracket check, but 1 + 2 + 3 could fail the precedence check depending on the validation rules.
Students forget that the linked-list stack for tree traversal uses a double pointer (stack **s). This is necessary because push and pop modify the head of the linked list, and C requires a pointer-to-pointer to modify a pointer passed by reference.
⚠️ Know the difference between depth-first (preorder, inorder, postorder) and breadth-first (level-order) traversals. Be able to produce the output for a given tree using each method.
⚠️ The child-push order (right before left for preorder stack) is a classic exam trick question. Expect to see it in a "what is wrong with this code" format.
⚠️ Level-order traversal is essentially BFS. If the exam asks about BFS on a tree, this is the answer.
⚠️ Expression validation combines two concepts (bracket matching and precedence). Exam questions may ask you to extend the balanced-parentheses function to also handle operators.
⚠️ Understand why the stack for tree traversal uses stack **s (double pointer) rather than stack *s. This is a pointer mechanics question that exams occasionally test independently.
True or False: In iterative preorder traversal, you push the left child before the right child.
Fill in the blank: Level-order traversal uses a ________ to process nodes layer by layer.
True or False: After a correct level-order traversal of the example tree (1, 2, 3, 4, 5), the output is 1 2 3 4 5.
Fill in the blank: The expression "(1 + 2 * 3" is invalid because it has an unmatched ________.
True or False: A double pointer (stack **s) is needed in push/pop when the stack itself is a linked list.
Answers: 1. False (you push right first, then left, so left gets popped first). 2. Queue. 3. True. 4. Opening parenthesis. 5. True.
Q: Given the tree below, what is the preorder output using an iterative stack-based traversal?
10
/ \
20 30
/
40
A: 10, 20, 40, 30. Push 10. Pop 10 (print). Push 30, push 20. Pop 20 (print). Push 40 (no right child). Pop 40 (print). Pop 30 (print).
Q: Using the same tree, what is the level-order output?
A: 10, 20, 30, 40. Enqueue 10. Dequeue 10 (print), enqueue 20 and 30. Dequeue 20 (print), enqueue 40. Dequeue 30 (print). Dequeue 40 (print).
Q: Why does is_valid_expression("(1 + 2) * 3") return true (1)?
A: The parentheses are balanced (push (, pop it when ) is hit, they match). The + is pushed, then popped when ) is processed. Then is pushed onto an empty stack (no precedence conflict). At the end, the only thing left is , but wait, the function returns s.top == -1. In the source implementation, * remains on the stack, so this would return false. The source's own test case claims it returns 1, which suggests the precedence-checking rules in this particular implementation are narrower than a full expression parser. For exam purposes, focus on understanding the bracket-matching logic and the precedence-comparison principle.
Q: What is the time complexity of level-order traversal on a binary tree with n nodes?
A: O(n). Every node is enqueued and dequeued exactly once.
Q: In the expression validator, what does precedence return for the character (?
A: 0. It is not *, /, +, or -, so it falls into the else branch. This means ( on the stack will never block an incoming operator's precedence check.
Preorder traversal connects to tree serialisation and reconstruction, which you may see in more advanced data structures courses. Level-order traversal is the tree-specific case of BFS, a graph algorithm you will study extensively in COP 3530 (Data Structures) or equivalent. Expression validation is a stepping stone to writing a full recursive-descent parser, a topic in compiler construction courses. The double-pointer pattern used for the linked-list stack (stack **s) is the same pattern used for any function that modifies the head of a linked list, which is worth revising in its own right.
preorder traversal, iterative preorder, level-order traversal, breadth-first search, BFS, binary tree, tree traversal, depth-first search, DFS, stack-based traversal, queue-based traversal, expression validation, operator precedence, balanced brackets, double pointer, linked list stack, COP 3502C, Computer Science I, UCF, C programming, tree algorithms