Binary Trees

Preorder, inorder, postorder traversals.

The idea

A binary tree is the standard structure for storing data hierarchically: a tree — one node designated the root, every other node attached to exactly one parent — in which each node has at most two children, distinguished as a left child and a right child. A node with no children is a leaf, and a node together with all its descendants is a subtree. Because the children are distinguished, a node with a single child must still specify which side that child is on.

A traversal visits every node exactly once. A binary tree consists of a root and two smaller binary trees, so the rule is recursive: traverse the left subtree, traverse the right subtree, and visit the node itself. The three standard orders differ only in when the node is visited.

- Preorder: node, then left subtree, then right subtree. - Inorder: left subtree, then node, then right subtree. - Postorder: left subtree, then right subtree, then node.

Preorder always begins at the root, and postorder always ends there.

Ways to work on it

• Walkthrough. Leaves and the three traversal orders.
• Practice. Produce a traversal of the tree.
• Hardest. Postorder, and why inorder is sorted for a BST.

Not sure where to start? Take the ten-question placement test.