You need to delete all nodes in a binary tree, freeing memory in an order that ensures children are always deleted before their parent. Which traversal should you use?
APreorder (root, left, right) — visit parent first, then children
BInorder (left, root, right) — balanced between parent and children
CPostorder (left, right, root) — visit both subtrees before the parent
DLevel-order — process nodes top to bottom by level
Postorder visits both child subtrees before the current node, which is exactly what's needed to safely delete a tree: you process and free all children before freeing the parent. Using preorder would free parents before children, creating dangling pointers. This is the canonical example of why traversal order matters: the application requirement (children before parents) maps directly onto postorder's structure.
Question 2 Multiple Choice
You perform an inorder traversal on a binary tree and get the sequence: 15, 7, 22, 3, 11. What can you conclude?
ANothing — inorder traversal of an arbitrary binary tree tells you nothing about whether it is a BST
BThe tree is a valid BST, because inorder traversal always produces sorted output
CThe tree is not a valid BST, because the output is not in sorted order
DYou need to also check the preorder output before drawing any conclusion
Inorder traversal of a binary search tree always produces sorted output. Since this output (15, 7, 22, 3, 11) is not sorted, the tree violates BST ordering. This question targets the misconception in option B: inorder produces sorted output ONLY for BSTs, not arbitrary binary trees. Knowing this, an unsorted inorder output is definitive proof the tree is not a valid BST.
Question 3 True / False
Inorder traversal of any binary tree produces elements in sorted order.
TTrue
FFalse
Answer: False
Inorder traversal produces sorted output ONLY for binary search trees, where the BST property guarantees the left subtree contains values smaller than the root and the right subtree contains larger values. For an arbitrary binary tree with no ordering constraint, inorder traversal simply visits left subtree, then root, then right subtree — the output order depends entirely on how values happen to be arranged, which may not be sorted.
Question 4 True / False
Preorder traversal visits a parent node before its children, which makes it naturally suited for copying a tree or producing a top-down representation of its structure.
TTrue
FFalse
Answer: True
Preorder's root-first order means you process every parent before its children, preserving the hierarchical structure from top to bottom. To copy a tree, you create each node before attaching its children — exactly the order preorder provides. Similarly, prefix expressions (operators before operands) in expression trees correspond to preorder traversal. This contrasts with postorder (bottom-up, useful for aggregates) and inorder (interleaves root between subtrees).
Question 5 Short Answer
What determines which depth-first traversal (preorder, inorder, or postorder) to use, and why does the order matter?
Think about your answer, then reveal below.
Model answer: The choice depends on the required relationship between a node and its children in the application. Preorder (root first) is used when a parent must be processed before its children — copying a tree, serializing structure, prefix expressions. Inorder (left, root, right) is used for sorted enumeration of a BST. Postorder (children first) is used when children must be processed before their parent — deletion, computing subtree aggregates like height or size.
The three traversals differ only in when the current node is visited relative to its children, but this single difference has significant practical consequences. The traversal order directly controls the sequencing of operations, and choosing the wrong order can produce incorrect results — freeing a parent before its children, or failing to get sorted output from a BST.