case the new node is added as the root of the tree in this casen is repainted blackas the root of the tree is always black since adds one black node to every path at onceproperty is not violated the code for case can be given as followsvoid case (struct node *nif ( -parent =null/root node -colour blackelse case ( )case the new node' parent is black in this caseboth children of every red node are blackso property is not invalidated property is also not threatened this is because the new node has two black leaf childrenbut because is redthe paths through each of its children have the same number of black nodes the code to check for case can be given as followsvoid case (struct node *nif ( -parent -colour =blackreturn/red black tree property is not violated*else case ( )in the following casesit is assumed that has grandparent node gbecause its parent is redand if it were the rootit would be black thusn also has an uncle node (irrespective of whether is leaf node or an internal nodecase if both the parent (pand the uncle (uare red in this caseproperty which says all paths from any given node to its leaf nodes have an equal number of black nodes is violated insertion in the third case is illustrated in fig in order to restore property both nodes ( and uare repainted black and the grandparent is repainted red nowthe new red node has black parent since any path through the parent or uncle must pass through the grandparentthe number of black nodes on these paths has not changed howeverthe grandparent may now violate property which says that the root node is always black or property which states that both children of every red node are black property will be violated when has red parent in order to fix this problemthis entire procedure is recursively performed on from case the code to deal with figure insertion in case case insertion is as follows