What is a binary tree and what are the common traversal orders?

• A. A binary tree node has up to two children; common traversals are in-order, pre-order, and post-order.
• B. A binary tree node has three children; traversals include in-order only.
• C. Binary trees are always complete.
• D. Binary trees cannot be traversed.

Answer: (A)

A binary tree is a structure where each node has at most two children, usually referred to as left and right. When we traverse such a tree, we visit nodes in specific orders to process or reproduce the data and structure.

In-order traversal visits the left subtree, then the node itself, and finally the right subtree. This order is especially useful for binary search trees because it yields the keys in sorted order.

Pre-order traversal visits the node first, then the left subtree, and then the right subtree. This is handy for copying or serializing the tree, since the node is processed before its descendants.

Post-order traversal visits the left subtree, then the right subtree, and finally the node. This is useful for deleting a tree safely (children before their parent) and for evaluating expressions in certain forms.

The other statements don’t fit the concept: a binary tree does not have three children, and binary trees are not required to be complete. And binary trees can be traversed using the three common orders above, among others.