Data Structures: Trees and Traversals Quiz

Part I: Multiple Choice Questions

• Question 1: Pre-order traversal is most helpful for reconstructing binary trees when combined with in-order traversal.

• Question 2: Leaf nodes in an expression tree typically represent variables or constants.

• Question 3: Operator nodes in expression trees perform computations on their child nodes.

• Question 4: Internal nodes in expression trees usually contain operators.

• Question 5: The expression tree for (3+2)×5 has a root node 'x' with children '+' and '5'.

• Question 6: A binary search tree (BST) is structured to keep a sorted order.

• Question 7: An AVL tree ensures the height difference between left and right subtrees of any node is at most 1.

• Question 8: In a complete binary tree, all levels (except potentially the final one) are completely filled from left to right.

• Question 9: A full binary tree has each level filled evenly. Every node has either zero or two children.

Additional Multiple Choice Questions

• Question 10: Heaps use complete binary trees.

• Question 11: AVL trees are balanced binary search trees.

• Question 12: A perfect binary tree has all leaf nodes on the same level.

• Question 13: Complete binary trees are frequently used in memory management.

• Question 14: AVL trees maintain balance after insertions or deletions.

• Question 15: Every node in a red-black tree is either red or black.

• Question 16: A leaf node has no children.

• Question 17: Pre-order traversal visits the root first, followed by the left subtree, and then the right subtree.

• Question 18: The maximum number of children a node in a binary tree can have is two.

• Question 19: Characteristics of a binary search tree (BST): left subtree values are smaller than the root and right subtree values are greater than the root.

• Question 20: A binary tree has a root and each node can have at most two children.

• Question 21: If a node has only one child, it is not a leaf node. It can have either a left or a right child, but not both.

• Question 22: Inserting a node into a binary tree that already has two children often involves reorganizing the tree.

• Question 23: Creating a binary tree node usually involves initializing the node with a value and setting its left and right pointers to null.

• Question 24: Insertion into a binary tree often guarantees that the tree remains a legal binary tree after insertion.

• Question 25: Tree traversal involves visiting every node to perform specific operations.

• Question 26: Pre-order traversal visits the root node initially before the subtrees.

• Question 27: Post-order traversal visits the root node last.

• Question 28: In-order traversal visits the left subtree, then the root, and finally the right subtree.

• Question 29: The order of node visitation in pre-order traversal is root, left subtree, right subtree.

• Question 30: Depth-first search methods, including pre-order and post-order, are also categorized as depth-first traversals.

• Question 31: Iterative traversal typically uses a stack data structure.

• Question 32: In post-order traversal, the root node is visited last.

• Question 33: Level-order traversal processes nodes level by level.

• Question 34: Nodes in a binary search tree are visited in ascending order in an in-order traversal.

• Question 35: Post-order traversal is commonly used to evaluate expressions in expression trees.

• Question 36: Huffman encoding uses full binary trees.

• Question 37: In a Binary Search Tree (BST), the left child's values are less than the parent, and the right child's values are greater.

• Question 38: A node with a value smaller than the root is placed in the left subtree.

• Question 39: A node with a value greater than the root is placed in the right subtree.

• Question 40: An in-order traversal can confirm whether a BST is properly sorted.