Binary Tree Insert and In-Order Traversal

An ordered binary tree of up to 10 positive integers is stored in a 2D array Tree. For each index: column 0 is the left pointer, column 1 is the data, column 2 is the right pointer. A null pointer is -1.

RootPointer starts at -1. FirstFree starts at 0 and increases by 1 each time a node is added. Nodes are never deleted.

Write:

• procedure AddNode(Value) — store the value in the next free node and link it into the tree so left children are smaller and right children are greater or equal. Output The tree is full if there is no space.
• procedure InOrder(NodeIndex) — recursively visit left, output the data, then visit right, so the values print in ascending order.

The harness reads a count, then that many integers, inserts each one, and prints the in-order traversal.

Input: A count, then that many integers. Output: The values in ascending order, one per line.

Example:

Input:  5
        20
        10
        26
        22
        8
Output: 8
        10
        20
        22
        26