Tree Structures, and the Prastāra as a Binary Tree

The tree, drawn by a program

def uddista(pattern):
    y = 1
    for ch in reversed(pattern):
        y *= 2
        if ch == "G":
            y -= 1
    return y

def draw(n, prefix="", depth=0):
    """The prastara as a binary tree. Every leaf is one pattern."""
    if depth == n:
        print("%s    pattern %s, prastara row %d" % ("    " * depth, prefix, uddista(prefix)))
        return
    for symbol in ("G", "L"):
        print("%s+-- %s" % ("    " * depth, symbol))
        draw(n, prefix + symbol, depth + 1)

print("root, no syllables chosen yet")
draw(3)
print()
print("leaves: 2**3 =", 2 ** 3, "   depth:", 3, "   internal nodes:", 2 ** 3 - 1)

root, no syllables chosen yet
+-- G
    +-- G
        +-- G
                pattern GGG, prastara row 1
        +-- L
                pattern GGL, prastara row 5
    +-- L
        +-- G
                pattern GLG, prastara row 3
        +-- L
                pattern GLL, prastara row 7
+-- L
    +-- G
        +-- G
                pattern LGG, prastara row 2
        +-- L
                pattern LGL, prastara row 6
    +-- L
        +-- G
                pattern LLG, prastara row 4
        +-- L
                pattern LLL, prastara row 8

leaves: 2**3 = 8    depth: 3    internal nodes: 7

The complication, which is the point of the chapter

Read the leaves top to bottom: rows 1, 5, 3, 7, 2, 6, 4, 8. That is not the prastāra order.

The reason is exact and it is worth being able to state. The tree's natural traversal fixes the FIRST syllable at the top and varies the LAST one fastest. The prastāra varies the FIRST syllable fastest. So the two orders differ, and they differ by reversing the significance of the positions.

Three ways to put it, all the same fact.

In tree terms. A depth-first traversal that chooses the first syllable at the root is a big-endian traversal, and the prastāra is little-endian.

In binary terms. The traversal enumerates 000, 001, 010, 011, 100, 101, 110, 111 with the first symbol as the most significant bit. The prastāra enumerates the same strings with the first symbol as the least significant.

In practical terms. If you want the tree's traversal to produce the prastāra, put the LAST syllable at the root. Then each level down fixes an earlier syllable, and the leaves come out in Piṅgala's order.

This is not a defect in either structure. It is the thing to be careful about, and a student who can say why the orders differ understands both.

What the tree is good for, and what it is not

Good for: reasoning about the count. The 2 to the power n leaves and the 2 to the power n plus one minus two edges both fall out of the picture in a line.

Good for: pruning. If you only want patterns with no two adjacent heavy syllables, you can abandon a subtree the moment the condition fails, and never visit its leaves. That is a saving the flat table cannot express, and it is how a search problem is usually attacked.

Not good for: storage. Holding the tree costs more than holding the table, because the internal nodes are stored too. The tree is a way of thinking, and the table is the answer.

Not good for: random access. There is no way to jump to the forty-first leaf of a tree without walking. That is what naṣṭa is for, and it is the one thing the tree makes harder rather than easier.

Quick revision

• Tree vocabulary: node, edge, root, parent, child, leaf, depth, height, path. Binary tree: at most two children. Complete binary tree of depth n: 2 to the power n leaves.
• The prastāra is the tree of n two-way choices; a pattern is a path from the root to a leaf.
• Leaves: 2 to the power n. Edges: 2 to the power n plus one, minus two, which is the running total sūtra's figure.
• The tree's natural traversal is big-endian and the prastāra is little-endian, so the leaf order is NOT the prastāra order. Put the last syllable at the root to fix it.
• The tree is good for counting and for pruning, bad for storage and for random access.

Test yourself

1. Define leaf, depth and complete binary tree, and say how many leaves a complete binary tree of depth 6 has.

A leaf is a node with no children. The depth of a node is the number of edges from the root to it. A complete binary tree of depth n has two children at every node above depth n and all its leaves at depth n. At depth 6 it has 64 leaves.

2. Why is the prastāra a binary tree, and what does a path represent?

Because a pattern is built by n successive two-way choices of syllable, so the set of patterns is the set of root-to-leaf paths in a complete binary tree of depth n. A path spells the pattern.

3. The tree's leaves come out as rows 1, 5, 3, 7, 2, 6, 4, 8. Explain why, and say how to fix it.

The traversal fixes the first syllable at the root, so the last syllable varies fastest, which makes the first syllable the most significant. The prastāra makes the first syllable the least significant. Putting the last syllable at the root makes the traversal produce Piṅgala's order.

4. Name one thing the tree makes easier than the flat table and one thing it makes harder.

Easier: pruning, since a subtree whose patterns cannot satisfy a condition can be abandoned without visiting its leaves. Harder: random access, since there is no way to jump to the forty-first leaf without walking, which is exactly what naṣṭa does arithmetically.