This line if code checks only the right child colour. It should check the left child as well. https://github.com/Bibeknam/algorithmtutorprograms/blob/705130fc0c5fb5c6bdc53967aea7de644e9bb2c5/data-structures/red-black-trees/RedBlackTree.cpp#L115