Stack applications and binary-tree reconstruction

Objectives and precise conventions

Apply an existing stack to postfix evaluation and delimiter matching, then use traversal order to reconstruct binary trees and reason about uniqueness and height. These are ordinary ordered binary trees, not necessarily BSTs: left and right child positions matter. All reconstruction labels are distinct unless a counterexample explicitly says otherwise. Height counts edges; empty tree has height −1, a leaf height 0. Full means every node has zero or two children, complete means all levels except possibly the last are filled and the last is filled left-to-right, and perfect means every internal node has two children and all leaves have equal depth. Do not substitute one word for another.

1. Postfix evaluation: operand order lives in the stack

Tokens are explicitly separated; "12" is one operand rather than operands 1 and 2. The examples use binary +,−,× and exact integer values small enough to avoid overflow. No division ambiguity occurs. Scan left-to-right. Push an operand. For a binary operator, require at least two entries, pop right operand b first, then left operand a, compute a op b and push the result. At the end exactly one value must remain. Too few operands during the scan is underflow; extra values at the end mean the token stream is not a single complete expression.

Worked trace for 8 3 2 * − 4 +, stack written bottom-to-top:

8 : [8] 3 : [8,3] 2 : [8,3,2]

• : [8,6]

− : [2] 4 : [2,4] + : [6]

At subtraction, b=6 and a=8, so push 2, not −2. For m tokens, every token is processed once, giving O(m) time and O(m) worst-case stack space. Actual maximum occupancy for this trace is 3. Counting operators/operands is necessary but not sufficient for validity: a binary-expression stream needs operands=operators+1, but + 2 3 satisfies the count and still underflows immediately. Unary operators would require a separately declared arity rule.

2. Balanced delimiters require type and nesting

For a stream containing (),[],{}, push each opening delimiter. On a closing delimiter require a nonempty stack and the matching opening delimiter at the top; then pop. Ignore other tokens under this simplified contract; recognizing quoted strings/comments in a full programming-language source requires lexical analysis and is outside this delimiter-only example. Accept only if the stack is empty at the end.

Worked scan of ([{}]): push (, then [, then {; } pops {, ] pops [, ) pops (, so accept. For ([)], ) arrives when the top is [, so reject immediately even though each delimiter type has equal opening/closing counts. For (() the scan ends with an unmatched opening delimiter. For )( the first closing delimiter underflows. A single integer counter suffices for one delimiter type only if every prefix count is nonnegative and the final count is zero; multiple types need nesting/type information, not just separate counts. Time O(m), auxiliary stack O(d), where d is maximum nesting depth and d≤m.

3. Traversal reconstruction with a split-defining inorder

Preorder visits root,left,right; inorder visits left,root,right; postorder visits left,right,root. With distinct labels and valid consistent traversal sequences, preorder plus inorder uniquely determines an ordered binary tree. Take the first preorder label as root, find it in inorder, and split inorder into left/right parts. Their sizes determine how many following preorder labels belong to each subtree. Recurse on those paired slices. Inorder plus postorder is likewise unique: last postorder is root, and subtree sizes determine the slices. When consuming postorder backward with a shared index, reconstruct right before left.

Worked example: preorder A B D E C F; inorder D B E A C F. Root A splits inorder into D B E and C F. The next three preorder labels B D E form the left subtree: root B, children D and E. Right preorder C F with inorder C F gives root C with no left child and right child F. The full postorder is D E B F C A and height is 2. This derivation uses left-subtree size, not alphabetical sorting; keys have no BST order here.

Validate before declaring a result: lengths and label sets must agree, labels must be distinct for this uniqueness theorem, and each chosen root must lie in the current inorder slice. Equal label sets alone do not ensure consistency. For example preorder A B C and inorder C A B are inconsistent: root A requires left-subtree label C, while preorder demands B in that one-node subtree. A linear search for each inorder root gives O(n²) worst-case reconstruction. With a label→inorder-position lookup having O(1) access, plus index ranges rather than repeated slice copies, construction is O(n) time and O(n) lookup storage, with O(h+1) recursion stack. A hash table gives expected O(1) lookup unless stronger guarantees are supplied.

4. Why preorder plus postorder can be ambiguous

For preorder A B and postorder B A, A is root and B its only child, but B may be left or right. Both ordered trees match. Thus preorder/postorder do not generally determine shape even with distinct labels. With distinct labels and a full binary tree contract, consistent preorder/postorder do determine a unique ordered tree: every nonleaf has two children, the next preorder root identifies the left subtree's endpoint in postorder, and the remainder belongs to the right subtree. That extra contract removes the one-child ambiguity; it must not be silently assumed for arbitrary trees. Repeated labels can also destroy uniqueness even when inorder is supplied, because a root label may have multiple candidate split positions.

5. Shape bounds connect back to traversal and stacks

At depth d a binary tree has at most 2^d nodes. Summing through edge-height h gives n≤2^(h+1)−1. For n≥1, ceil(log2(n+1))−1≤h≤n−1; the maximum is a chain, and a minimum-height shape fills enough upper levels. These bounds do not assert that every n-node tree has logarithmic height. A complete n-node tree has h=floor(log2 n). A full binary tree with I internal nodes has L=I+1 leaves and n=2I+1, because 2I child edges equal n−1 total edges. Full trees need not be perfect or have logarithmic height: a comb-shaped full tree can have height linear in n.

For n=7, ordinary binary-tree heights can range from 2 to 6. A seven-node full tree can have height 3, so full does not imply height 2. A recursive traversal/reconstruction on a chain uses O(n) stack depth; on a balanced-height tree it uses O(log n). Do not confuse O(n) total visits with O(n) simultaneous stack entries in every shape.

Pitfall checklist

Declare token boundaries and operator arity; pop right before left. Validate delimiters at each close and again at the end. For reconstruction state distinctness, traversal pair and any full-tree promise. Check slice consistency before claiming uniqueness. For height formulas declare edges versus nodes, and distinguish the tree's actual shape from a possible minimum-height shape.

Original practice: six single-correct MCQs

These original teaching questions are not previous-year questions. Choose one answer.

P01. Evaluate postfix 8 3 2 * − 4 + with binary operators.

A. −6 B. 2 C. 6 D. 10

Answer: C

A: This reverses or misorders operands.

B: This is the intermediate value before adding 4.

C: 3×2=6, then 8−6=2, then 2+4=6.

D: The postfix grouping is (8−3×2)+4.

P02. Which delimiter string is rejected despite equal opening/closing counts for every type?

A. ([]) B. ([)] C. {()} D. [{}]

Answer: B

A: Types and nesting match.

B: At ), the top is [, so the nesting is wrong.

C: Types and nesting match.

D: Types and nesting match.

P03. Preorder A B D E C F and inorder D B E A C F give which postorder?

A. D E B F C A B. D B E F C A C. A B D E C F D. D E B C F A

Answer: A

A: Left subtree D,E,B; right subtree F,C; root A last.

B: B must follow both children in postorder.

C: This is preorder, not postorder.

D: F is the right child of C and must precede C.

P04. Distinct labels, preorder A B and postorder B A, with no full-tree promise, determine:

A. Exactly one ordered tree B. No valid tree C. A unique BST D. Two ordered tree shapes

Answer: D

A: The side of the sole child is not specified.

B: Both one-child placements are valid.

C: No BST ordering contract was supplied.

D: B can be either the left or right child of A.

P05. For an ordinary seven-node binary tree, possible minimum and maximum edge-heights are:

A. 3 and 7 B. 2 and 6 C. 2 and 2 D. 0 and 6

Answer: B

A: These count path nodes rather than edges.

B: A perfect shape has height 2; a chain has height 6.

C: Not all shapes are perfect or balanced.

D: Height zero holds only one node.

P06. A full binary tree has 9 internal nodes. How many leaves?

A. 9 B. 18 C. 10 D. 19

Answer: C

A: A full tree has one more leaf than internal nodes.

B: 18 is the number of child edges.

C: L=I+1=10.

D: 19 is the total node count 2I+1.

Sources and scope

GATE CS 2026 bounded extension of existing foundations. Not a whole-subject completion claim. Examples and questions are original.

• Official GATE 2026 CS syllabus, Section 4