Binary tree challenge - "Corona Vaccine" - giving incorrect answer for a testcase

I am trying to solve the GeeksForGeeks challenge "Corona Vaccine", and it gives me wrong answer for a testcase mentioned below:

> Challenge:
>
> Geek has developed an effective vaccine for Corona virus and he wants each of the N houses in Geek Land to have access to it. Given a binary tree where each node represents a house in Geek Land, find the minimum number of houses that should be supplied with the vaccine kit if one vaccine kit is sufficient for that house, its parent house and it's immediate child nodes.
>
> Example:
>
> 1
> /
> 2 3
>
> 4
>
> 5
>
> 6
>
> Output:
>
> 2
>
> Explanation:
>
> The vaccine kits should be supplied to house numbers 1 and 5.

My code:

class Solution{
    public static int supplyVaccine(Node root){
        Map<Node,Integer> map = new HashMap<>();
        dfs(root, map);
        return map.get(root);
    }
    
    private static int dfs(Node root, Map<Node, Integer> map){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            map.put(root, 1);
            return 1;
        }
        int left = dfs(root.left, map);
        int right = dfs(root.right, map);
        int sum1 = left + right;
        int sum2 = 1;
        if(root.left != null){
            if(root.left.left != null){
                sum2 += map.get(root.left.left);
            }
            
            if(root.left.right != null){
                sum2 += map.get(root.left.right);
            }
        }
        
        if(root.right != null){
            if(root.right.left != null){
                sum2 += map.get(root.right.left);
            }
            
            if(root.right.right != null){
                sum2 += map.get(root.right.right);
            }
        }
        
        map.put(root, Math.min(sum1, sum2));
        
        return sum2;
    }
}

Brief about my approach:

• So, as in the question it states, if a node has the vaccine, it can give it to parent, itself and it's kids.

• When we are on a node, taken minimum of (current node + grandchildren, current left kid + current right kid).

• I am using a map to remember what value was stored for which node.

Testcase where my code errors out:

746 362 98 1519 1443 1811 90 825 1355 1199 1393 355 1061 1473 687 1905 32 266 1337 1218 842 712 1221 1012 590 775 1270 1162 780 1335 1493 723 321 1479 485 873 1218 1190 290 792 128 834 591 115 493 657 670 1757 130 1951 373 1925 1606 94 1384 509 945 248 1130 493 940 942 1214 746 567 948 1436 774 827 893 1022 1828 1144 1867 451 84 1925 1546 951 1498 1382 840 1672 781 51 1201 1304 1167 1052 509 1768 1034 1025 1004 509 927 195 741 321 1547 592 1956 1841 785 202 990 16 1357 798 660 609 319 30 1658 1276 60 1647 1620 220 269 1259 629 963 1116 805 1337 1329 100 1495 1225 1861 641 1247 1908 262 1362 219 1471 772 1134 1265 883 180 1386 294 1132 592 828 678 1 1252 1529 1952 239 1058 1627 72 419 869 515 1175 1366 783 870 543 1453 537 732 526 971 1579 867 962 1662 445 319 132 248 1625 1581 179 94 1394 833 1071 756 329 1155 1196 1369 1653 730 1148 766 29 592 747 1027 1867 1287 125 1466 1513 60 1062 1740 1821 247 1361 140 701 794 313 87 1842 1266 600 1058 1036 1478 1061 691 441 1484 325 199 1716 908 1274 1821 815 1113 166 169 1405 1631 1180 942 1272 1612 1560 1518 497 1197 100 1758 1324 1799 1329 69 1879 1938 852 1466 1534 757 1584 607 1943 1448 600 1762 1039 1633 1228 1900 429 433 1866 1307 267 219 254 230 396 788 1501 648 537 1101 681 1051 548 860 931 1050 237 1453 1608 1547 422 1600 1611 315 195 N 390 1143 955 824 479 80 1176 1136 164 1861 390 1243 1077 56 1784 934 206 1273 1811 685 1789 1092 313 1361 273 124 446 1748 1170 128 277 459 720 858 749 159 984 1102 883 1641 1457 500 1035 1632 950 75 1945 1391 1146 1703 1792 1951 883 458 545 278 970 431 1221 533 1424 591 1891 50 223 1118 390 1531 239 591 1354 118 411 1954 1169 1307 218 966 1708 1160 1775 1803 1544 74 848 1723 1174 1799 255 1814 1407 508 1356 1142 1494 280 1771 1950 1119 1909 1163 1029 1877 876 661 1686 1910 1683 161 1648 2 1653 1909 1909 732 1193 765 946 1553 579 198 796 163 1367 1244 1549 1321 1339 994 470 1270 1573 818 1064 1227 1857 1262 1667 164 192 1807 213 148 975 857 1900 612 1917 1545 939 224 45 1490 798 937 805 286 1133 450 44 1166 989 749 1260 866 400 1037 554 1568 886 1908 1135 1229 1078 706 1918 1736 1095 1550 287 382 1952 1264 409 1406 1021 206 1417 1155 1267 978 1451 185 1705 1084 913 1883 1347 959 262 682 538 328 1541 295 581 152 1298 896 1634 1682 346 875 1252 1292 1210 1582 449 1113 217 1512 937 288 928 1122 1066 1227 1318 117 1025 1478 619 1481 378 24 1237 1113 1202 712 532 1492 221 660 1669 737 1758 508 603 1413 1600 1115 97 1162 1428 1917 512 621 863 1845 1627 1377 259 825 441 940 1686 1272 1634 1187 746 1237 659 1582 843 1874 2 1038 1602 1064 984 1003 355 625 275 877 1098 1625 110 925 441 1847 1474 709 894 790 N 489 1796 1534 1336 1788 176 1872 1043 438 1870 501 722 707 1885 1612 583 168 1771 1101 74 718 1299 489 570 273 147 564 1869 519 1020 1884 1512 235 1263 927 579 1337 392 1159 945 825 1153 924 1211 569 1583 495 1943 1809 199 1522 142 410 963 749 150 424 767 434 1603 64 1134 94 1915 390 1822 1852 493 1597 854 1237 650 444 877 1292 840 602 1787 610 1076 5 1263 1797 274 579 789 1743 1836 1789 895 166 534 260 850 800 1655 957 293 393 1425 1023 1823 574 1233 504 876 374 980 710 233 1259 1855 1143 1222 700 592 800 179 1006 32 210 971 1261 1084 3 317 1601 1853 836 1424 1008 959 313 1870 226 781 1812 1515 1850 781 788 853 635 453 1856 672 1402 1474 1784 307 628 401 1193 1620 416 201 1440 1682 1420 1348 812 116 389 611 287 280 1450 1936 834 654 130 959 1024 564 1291 1144 45 212 1130 1760 838 1057 730 833 458 246 938 1021 1285 1634 713 1493 1264 1049 1634 476 1640 241 1246 893 1707 1543 323 1842 516 1837 622 1814 274 192 752 471 789 763 805 1867 1049 165 647 48 565 932 274 1758 1487 1494 1027 1288 723 1867 269 1765 1797 952 289 821 1469 709 1249 1409 825 1219 596 1088 1374 965 150 116 506 289 413 264 719 76 1363 1466 22 1093 1450 741 624 341 621 286 649 1473 1777 400 117 1588 1131 1265 444 816 553 1670 1423 59 12 944 412 1312 86 420 220 1058 354 1231 653 485 695 309 1480 1481 1648 N 1924 1607 1471 107 1777 88 1110 389 1806 1355 606 426 948 300 175 247 857 1436 662 1214 1320 751 1071 353 1247 35 613 496 1880 1889 40 1105 747 1133 32 1214 1213 1515 1438 565 376 244 486 557 253 1275 1472 683 43 1236 721 1478 139 1318 559 1186 514 113

My output:

272

Expected Output:

271

Note: Testcases are made in a level order traversal way for the tree.

Minimum reproducible example: https://ideone.com/WJJfd5

Here is a smaller example tree for which your code returns the wrong result:

      1
     / \
    2   3
   /     \
  4       7
 /  
8

The optimal solution is 2 (nodes 4 and 3), but your code returns 3 (implying that it includes the root). When your code comes back from the recursive calls made at the root, all nodes (except the root) will have a value of 1 in map. The return values of the recursive calls are both 1.

But then the algorithm looks at the grandchildren of the root and sees two nodes, counting for 2. It includes the root node (sum2 = 1) and so arrives at 3. But again, this is wrong, because the node 3 can take care of the right subtree including the root.

So you need a different algorithm.

Proposed algorithm

You can use states for each node and drop the Map. We could for instance use three colors for that (white, black, grey). The meaning of these colors is:

• Black: this node must be marked (it represents a house with a vaccine kit)
• Grey: this node has a child that is marked and does not need to be marked itself
• White: any other node. This is a node that must be covered by a marked parent, or must itself be marked (when it has no parent)

Here is how to assign those colors in a post order traversal:

• Consider null as Grey.
• White: the node has only grey children. (The leaves of the tree are all in this case).
• Black: the node has at least one white child.
• Grey: any other node

Black nodes count towards the result (they represent houses with vaccine kits).

If the root happens to be white, it also counts towards the result. Other white nodes are covered by their black parents, but as a root has no parent, it is not covered when it is white.

Here is an implementation of that idea:

class Solution{
    static final int WHITE = 0;
    static final int GREY = 1;
    static final int BLACK = 2;
    
    static int result;
    
    public static int supplyVaccine(Node root){
        result = 0; // dfs will update this counter as a side effect.
        return (dfs(root) == WHITE ? 1 : 0) + result;
    }
    
    private static int dfs(Node root){
        if (root == null) return GREY;
        int left = dfs(root.left);
        int right = dfs(root.right);
        // Apply rules, and return color assigned to root
        if (left == GREY && right == GREY) return WHITE;
        if (left != WHITE && right != WHITE) return GREY;
        result++;
        return BLACK;
    }
}