increasing order of their weights. A leaf block always precedes internal block of same weight, thus maintaining the invariant. NYT (Not Yet Transferred) is special node and used to represents symbols which are 'not yet transferred'. algorithm for adding a symbol is leaf_to_increment := NULL p := pointer to the leaf node containing the next symbol if (p is NYT) then Extend p by adding two children Left child becomes new NYT and right child is the new symbol leaf node p := parent of new symbol leaf node leaf_to_increment := Right Child of p else Swap p with leader of its block if (new p is sibling to NYT) then leaf_to_increment := p p := parent of p while (p ≠ NULL) do Slide_And_Increment(p) if (leaf_to_increment != NULL) then Slide_And_Increment(leaf_to_increment) function Slide_And_Increment(p) is previous_p := parent of p if (p is an internal node) then Slide p in the tree higher than the leaf nodes of weight wt + 1 increase weight of p by 1 p := previous_p else Slide p in the tree higher than the internal nodes of weight wt increase weight of p by 1 p := new parent of p. Encoder and decoder start with only the root node, which has the maximum number. In the beginning it is our initial NYT node. When we transmit an NYT symbol, we have to transmit code for the NYT node, then for its generic code. For every symbol that is already in the tree, we only have to transmit code for its leaf node. Example Encoding "abb" gives 01100001 001100010 11. Step 1: Start with an empty tree. For "a" transmit its binary code. Step 2: NYT spawns two child nodes: 254 and 255, both with weight 0. Increase weight for root and 255. Code for "a", associated with node 255, is 1. For "b" transmit 0 (for NYT node) then its binary code. Step 3: NYT spawns two child nodes: 252 for NYT and 253 for leaf node, both with weight 0. Increase weights for 253, 254, and root. To maintain Vitter's invariant that all leaves of weight w precede (in the implicit numbering) all internal nodes of weight w, the branch starting with node 254 should be swapped (in terms of symbols and weights, but not number ordering) with node 255. Code for "b" is 11. For the second "b" transmit 11. For the