Pre-order vs post-order traversal index

post-order-index.md

Post-order index from Pre-order index

The purpose of this paper is to demonstrate that you can derive the post-order index of a node from the pre-order index of the node if you know the depth of the node (called parent count) and the node's total number of children (called child count).

Definitions

Using a tree as defined here.

The pre-order index of a node is the index at which the node would reside if the all the nodes of a tree are appended into an array in using a pre-order traversal.

The post-order index of a node is the index at which the node would reside if the all the nodes of a tree are appended into an array in using a post-order traversal.

The child count of an a node is the number of children plus their child count's. That is, the child count is the number of nodes that have the node as a parent either directly or indirectly. A node with no children has a child count of 0.

Calculating indexes

Calculating pre-order index:

• The pre-order index of an the root node of a tree is 0.
• The pre-order index of the first child of a node is the pre-order index of node + 1.
• The pre-order index of the n-th child of a node that is not the first node is the child index of the previous child node + its child count + 1.

Calculating post-order index:

• The base index of the root node is 0.
• The base index of the first child node of a node is the base index of node.
• The base index of the n-th child of a node that is not the first node is the base index of the previous child node plus its child count + 1.
• The post-order index of a node is base index + child-count.

For the purpose of this calculation then parent count is the number from the node to the root node. It is what referred to here as depth but it is 0 based instead of 1 based.

Calculating pre-order index from using base-index:

• The pre-order index is base index + parent count

Calculating post-order index from pre-order index:

• The post-order index is pre-order index - parent count + child count.

Informal proofs

Pre-order index

Assume a pre-order traversal of something like:

interface Node {
  children: Node[];
  index?: number
}

function preOrderTraversal(node: Node, array: Node[]) {
  node.index = array.length;
  array.push(node);
  for (const child of node.children) {
    preOrderTraversal(child, array);
  }
}

let root: Node;
preOrderTraversal(root, []);

• The pre-order index of an the root node of a tree is 0.

  • The length of the aray passed into the initial call to preOrderTraversal() is of length 0 and the value of node is root therefore root's index will always be set to 0.

• The pre-order index of the first child of a node is the pre-order index of the node + 1.

  • node's index is set to the size of the array preOrderTraversal is called with.
  • The first call to preOrderTraversal in the for loop will pass an array that is one greater length than node was called with.
  • Therefore first child's index will be set to the length of this array which is one greater than the node's index.

• The pre-order index of the n-th child of a node that is not the first node is the pre-order index of the previous child node + its child count + 1.

  • Lemma: The length of array passed into any call to preOrderTraversal() is incremented by the child count of the node + 1.
    • array is incremented by at least 1 because node is added to the array.
    • If the node has no children then this lemma is satisified.
    • If this lemma is true then the for loop will increment the length of array by the child's child count + 1 for each child which is equal to the child count of node (by definition).
    • Therefore, by induction, preOrderTraversal() increments the array by the node's child count + 1.
  • The pre-order index of the child in the loop is the length of the array at the beginning of the loop.
  • Given the lemma the length of the array at the beginning of each iteration of the for loop is the pre-order index of the previous child of the for loop + it's child count + 1.
  • The previous child in the for loop is the previous child node (by definition).
  • Therefore the pre-order index of the n-th child of a node that is not the first node is the pre-order index of the previous child node + its child count + 1.

Post-order index

Assume a post-order traversal of something like:

interface Node {
  children: Node[];
  index?: number
}

function postOrderTraversal(node: Node, array: Node[]) {
  for (const child of node.children) {
    preOrderTraversal(child, array);
  }
  node.index = array.length;
  array.push(node);
}

let root: Node;
postOrderTraversal(root, []);

For the purpose of this proof, the base index of a node the length of array at the beginning of postOrderTraversal().

• The base index of the root node is 0.
  • The length of array passed into the initial call to postOrderTraversal() is of length 0.
  • In the initial call root is the value of node.
  • Therefore the root node's base index is 0.
• The base index of the first child node of a node is the base index of the node.
  • array is ummodified during first iteration of the for loop.
  • Therefore the base index of the first child node of node is the base index of node.
• The base index of the n-th child of a node that is not the first node is the base index of the previous child node + its child count + 1.
  • Lemma 1: The length of array passed into any call to postOrderTraversal() is incremented by the child count of the node + 1.
    • array is incremented by at least 1 because node is added to the array.
    • If the node has no children then this lemma is satisified.
    • If this lemma is true then the for loop will increment the length of array by the child's child count + 1 for each child which is equal to the child count of node (by definition).
    • Therefore, by induction, postOrderTraversal() increments the array by the node's child count + 1.
  • The base index of the child in the loop is the length of the array at the beginning of the loop.
  • Given lemma 1 the length of the array at the beginning of each iteration of the for loop is the base index of the previous node of the for loop + it's child count + 1.
  • The previous node in the for loop is the previous child node (by definition).
  • Therefore the base index of the n-th child of a node that is not the first node is the base index of the previous child node + its child count + 1.
• The post-order index of a node is base index + child-count.
  • Lemma 2: Calling postOrderTraversal() on all the children of a node will increment the length of array by the child count of the node.
    • Calling postOrderTraversal() on child increments it by the child count of the child + 1 by lemma 1.
    • Calling postOrderTraversal() on each child increments by the sum of the child counts of each child plus the number of children which is child count by definition.
  • The for loop increments array by child count of node by lemma 2.
  • index is set to the length of array after the loop which is base index + child count.

Pre-order using base index

• The pre-order index is base index + parent count
  • Lemma 3: base index of a node is the pre-order index - parent count.
    • by definition for the root node (0 = 0 - 0)
    • for the first child:
      • The pre-order index of the first child of a node is the pre-order index of the node + 1 (from above).
      • The base index of the first child node of a node is the base index of node (from above).
      • The difference for the first node is 1.
    • for all other nodes:
      • The pre-order index of the n-th child of a node that is not the first node is the pre-order index of the previous. child node plus its child count + 1 (from above).
      • The base index of the n-th child of a node that is not the first node is the base index of the previous child node plus its child count + 1 (from above).
      • Because the first node is different by one the difference between the base index and the pre-order index of each child is 1.
    • Therefore the difference between base index and pre-order index for each 1 for each parent of node which is parent count, by definition.
    • Therefore the base index of a node is pre-order index - parent count.
  • if base index = pre-order index - parent count, by algebra, pre-order index = base index + parent count.

Post-order using pre-order

• The post-order index is pre-order index - parent count + child count.
  • post-order index = base index + child count (from above).
  • pre-order index = base index + parent count (from above)
  • base index = pre-order index - parent count (algebra)
  • post-order index = pre-order index - parent count + child count (substitution)