Calling D(XXXXXXXXXX, 0) - Nodes left: sXXXXXXXXX Node = 0. Comp = -AAABBBCCC. Key = 1111111110 0x03fe Will be using recursion. - Nodes left: -sXXXXXXXX Node = 1. Comp = --AA------. Key = 0000001100 0x000c Will be using recursion. - Nodes left: --sXXXXXXX Node = 2. Comp = ---A------. Key = 0000001000 0x0008 Will be using recursion. - Nodes left: ---sXXXXXX Node = 3. Comp = ----------. Key = 0000000000 0x0000 Base case: No components left: 1 + Nodes left: --sXXXXXXX Node = 2. Key = 0000001000 0x0008 Putting 1 into cache & returning. + Nodes left: -sXXXXXXXX Node = 1. Key = 0000001100 0x000c Putting 1 into cache & returning. - Nodes left: -XXXsXXXXX Node = 4. Comp = -----AA---. Key = 0001100000 0x0060 Will be using recursion. - Nodes left: -XXX-sXXXX Node = 5. Comp = ------A---. Key = 0001000000 0x0040 Will be using recursion. - Nodes left: -XXX--sXXX Node = 6. Comp = ----------. Key = 0000000000 0x0000 Base case: No components left: 1 + Nodes left: -XXX-sXXXX Node = 5. Key = 0001000000 0x0040 Putting 1 into cache & returning. + Nodes left: -XXXsXXXXX Node = 4. Key = 0001100000 0x0060 Putting 1 into cache & returning. - Nodes left: -XXXXXXsXX Node = 7. Comp = --------AA. Key = 1100000000 0x0300 Will be using recursion. - Nodes left: -XXXXXX-sX Node = 8. Comp = ---------A. Key = 1000000000 0x0200 Will be using recursion. - Nodes left: -XXXXXX--s Node = 9. Comp = ----------. Key = 0000000000 0x0000 Base case: No components left: 1 + Nodes left: -XXXXXX-sX Node = 8. Key = 1000000000 0x0200 Putting 1 into cache & returning. + Nodes left: -XXXXXXsXX Node = 7. Key = 1100000000 0x0300 Putting 1 into cache & returning. + Nodes left: sXXXXXXXXX Node = 0. Key = 1111111110 0x03fe Putting 6 into cache & returning. Calling D(XXXXXXXXXX, 1) - Nodes left: XsXXXXXXXX Node = 1. Comp = A-BBAAAAAA. Key = 1111111101 0x03fd Will be using recursion. - Nodes left: s-XXXXXXXX Node = 0. Comp = ----AAABBB. Key = 1111110000 0x03f0 Will be using recursion. - Nodes left: --XXsXXXXX Node = 4. Comp = -----AA---. Key = 0001100000 0x0060 In Cache: 1 - Nodes left: --XXXXXsXX Node = 7. Comp = --------AA. Key = 1100000000 0x0300 In Cache: 1 + Nodes left: s-XXXXXXXX Node = 0. Key = 1111110000 0x03f0 Putting 2 into cache & returning. - Nodes left: X-sXXXXXXX Node = 2. Comp = ---A------. Key = 0000001000 0x0008 In Cache: 1 + Nodes left: XsXXXXXXXX Node = 1. Key = 1111111101 0x03fd Putting 4 into cache & returning. Calling D(XXXXXXXXXX, 2) - Nodes left: XXsXXXXXXX Node = 2. Comp = AA-BAAAAAA. Key = 1111111011 0x03fb Will be using recursion. - Nodes left: Xs-XXXXXXX Node = 1. Comp = A---AAAAAA. Key = 1111110001 0x03f1 Will be using recursion. - Nodes left: s--XXXXXXX Node = 0. Comp = ----AAABBB. Key = 1111110000 0x03f0 In Cache: 2 + Nodes left: Xs-XXXXXXX Node = 1. Key = 1111110001 0x03f1 Putting 2 into cache & returning. - Nodes left: XX-sXXXXXX Node = 3. Comp = ----------. Key = 0000000000 0x0000 In Cache: 1 + Nodes left: XXsXXXXXXX Node = 2. Key = 1111111011 0x03fb Putting 4 into cache & returning. Calling D(XXXXXXXXXX, 3) - Nodes left: XXXsXXXXXX Node = 3. Comp = AAA-AAAAAA. Key = 1111110111 0x03f7 Will be using recursion. - Nodes left: XXs-XXXXXX Node = 2. Comp = AA--AAAAAA. Key = 1111110011 0x03f3 Will be using recursion. - Nodes left: Xs--XXXXXX Node = 1. Comp = A---AAAAAA. Key = 1111110001 0x03f1 In Cache: 2 + Nodes left: XXs-XXXXXX Node = 2. Key = 1111110011 0x03f3 Putting 2 into cache & returning. + Nodes left: XXXsXXXXXX Node = 3. Key = 1111110111 0x03f7 Putting 2 into cache & returning. Calling D(XXXXXXXXXX, 4) - Nodes left: XXXXsXXXXX Node = 4. Comp = AAAA-BBAAA. Key = 1111101111 0x03ef Will be using recursion. - Nodes left: sXXX-XXXXX Node = 0. Comp = -AAA---BBB. Key = 1110001110 0x038e Will be using recursion. - Nodes left: -sXX-XXXXX Node = 1. Comp = --AA------. Key = 0000001100 0x000c In Cache: 1 - Nodes left: -XXX-XXsXX Node = 7. Comp = --------AA. Key = 1100000000 0x0300 In Cache: 1 + Nodes left: sXXX-XXXXX Node = 0. Key = 1110001110 0x038e Putting 2 into cache & returning. - Nodes left: XXXX-sXXXX Node = 5. Comp = ------A---. Key = 0001000000 0x0040 In Cache: 1 + Nodes left: XXXXsXXXXX Node = 4. Key = 1111101111 0x03ef Putting 4 into cache & returning. Calling D(XXXXXXXXXX, 5) - Nodes left: XXXXXsXXXX Node = 5. Comp = AAAAA-BAAA. Key = 1111011111 0x03df Will be using recursion. - Nodes left: XXXXs-XXXX Node = 4. Comp = AAAA---AAA. Key = 1110001111 0x038f Will be using recursion. - Nodes left: sXXX--XXXX Node = 0. Comp = -AAA---BBB. Key = 1110001110 0x038e In Cache: 2 + Nodes left: XXXXs-XXXX Node = 4. Key = 1110001111 0x038f Putting 2 into cache & returning. - Nodes left: XXXXX-sXXX Node = 6. Comp = ----------. Key = 0000000000 0x0000 In Cache: 1 + Nodes left: XXXXXsXXXX Node = 5. Key = 1111011111 0x03df Putting 4 into cache & returning. Calling D(XXXXXXXXXX, 6) - Nodes left: XXXXXXsXXX Node = 6. Comp = AAAAAA-AAA. Key = 1110111111 0x03bf Will be using recursion. - Nodes left: XXXXXs-XXX Node = 5. Comp = AAAAA--AAA. Key = 1110011111 0x039f Will be using recursion. - Nodes left: XXXXs--XXX Node = 4. Comp = AAAA---AAA. Key = 1110001111 0x038f In Cache: 2 + Nodes left: XXXXXs-XXX Node = 5. Key = 1110011111 0x039f Putting 2 into cache & returning. + Nodes left: XXXXXXsXXX Node = 6. Key = 1110111111 0x03bf Putting 2 into cache & returning. Calling D(XXXXXXXXXX, 7) - Nodes left: XXXXXXXsXX Node = 7. Comp = AAAAAAA-BB. Key = 1101111111 0x037f Will be using recursion. - Nodes left: sXXXXXX-XX Node = 0. Comp = -AAABBB---. Key = 0001111110 0x007e Will be using recursion. - Nodes left: -sXXXXX-XX Node = 1. Comp = --AA------. Key = 0000001100 0x000c In Cache: 1 - Nodes left: -XXXsXX-XX Node = 4. Comp = -----AA---. Key = 0001100000 0x0060 In Cache: 1 + Nodes left: sXXXXXX-XX Node = 0. Key = 0001111110 0x007e Putting 2 into cache & returning. - Nodes left: XXXXXXX-sX Node = 8. Comp = ---------A. Key = 1000000000 0x0200 In Cache: 1 + Nodes left: XXXXXXXsXX Node = 7. Key = 1101111111 0x037f Putting 4 into cache & returning. Calling D(XXXXXXXXXX, 8) - Nodes left: XXXXXXXXsX Node = 8. Comp = AAAAAAAA-B. Key = 1011111111 0x02ff Will be using recursion. - Nodes left: XXXXXXXs-X Node = 7. Comp = AAAAAAA---. Key = 0001111111 0x007f Will be using recursion. - Nodes left: sXXXXXX--X Node = 0. Comp = -AAABBB---. Key = 0001111110 0x007e In Cache: 2 + Nodes left: XXXXXXXs-X Node = 7. Key = 0001111111 0x007f Putting 2 into cache & returning. - Nodes left: XXXXXXXX-s Node = 9. Comp = ----------. Key = 0000000000 0x0000 In Cache: 1 + Nodes left: XXXXXXXXsX Node = 8. Key = 1011111111 0x02ff Putting 4 into cache & returning. Calling D(XXXXXXXXXX, 9) - Nodes left: XXXXXXXXXs Node = 9. Comp = AAAAAAAAA-. Key = 0111111111 0x01ff Will be using recursion. - Nodes left: XXXXXXXXs- Node = 8. Comp = AAAAAAAA--. Key = 0011111111 0x00ff Will be using recursion. - Nodes left: XXXXXXXs-- Node = 7. Comp = AAAAAAA---. Key = 0001111111 0x007f In Cache: 2 + Nodes left: XXXXXXXXs- Node = 8. Key = 0011111111 0x00ff Putting 2 into cache & returning. + Nodes left: XXXXXXXXXs Node = 9. Key = 0111111111 0x01ff Putting 2 into cache & returning. 36