Binary Tree Axioms, Degree Theorems & Traversal Reconstruction

Let T be an arbitrary binary tree with n nodes and E edges. Partition the nodes by their out-degree (number of children):

- n_0: Nodes with 0 children (Leaves).

- n_1: Nodes with 1 child.

- n_2: Nodes with 2 children.

Total nodes: n = n_0 + n_1 + n_2.

Proof of Degree Relation:

1. Every node in a tree except the root has exactly 1 incoming edge. Therefore: E = n - 1.

2. Each degree-1 node contributes 1 outgoing edge, and each degree-2 node contributes 2 outgoing edges. Therefore: E = n_1 + 2 * n_2.

3. Equating the two expressions for E:

n - 1 = n_1 + 2 * n_2

(n_0 + n_1 + n_2) - 1 = n_1 + 2 * n_2

n_0 - 1 = n_2 implies n_0 = n_2 + 1.

This fundamental law holds unconditionally for every binary tree.

There are four standard systematic traversal strategies:

1. Pre-Order (N-L-R): Visit Node, traverse Left subtree, traverse Right subtree.

2. In-Order (L-N-R): Traverse Left subtree, visit Node, traverse Right subtree.

3. Post-Order (L-R-N): Traverse Left subtree, traverse Right subtree, visit Node.

4. Level-Order: Breadth-First traversal using a FIFO queue.

Reconstruction Theorem:

- Pre-order's first element is always the root. Locate this root in the In-order traversal. All elements to the left of the root in In-order belong to the left subtree; all elements to the right belong to the right subtree. Recursively reconstruct.

- Why Pre-order + Post-order fails: If a node has a single child, Pre-order [A, B] and Post-order [B, A] cannot determine whether B is a left child or a right child.