In this home exercise you will work with red$-$black trees, which you already know from the lecture.

In order to verify the correctness of a tree, a checker should first be implemented which checks the passed red$-$black tree for the following properties:

$($a$)$ Rule $1$: Each node has a color and the attribute is either red or black. $($b$)$ Rule $2$: The root is black.

$($c$)$ Rule $3$: Red nodes have no red children $($no two red nodes may follow each other$).($d$)$ Rule $4$: Every path from a node to its leaves contains the same number of black nodes.

To do this, complete the RBTreeChecker class. Throw an RBTreeException once you find a rule violation. What message you return in the exception is up to you.

You may only iterate over the tree once to check a rule: Iterating over the tree multiple times, for example to recalculate the black height for each node, is not permitted. Specifically, this means that the getLeft or getRight method may only be called once on each node during a method run$1.$ Please note that each rule should be considered individually: If another rule is violated, but the currently checked rule is correct, then no exception should be thrown.

Note: How you solve the task is up to you. However, changing the method signatures is not permitted.

package p$2.$binarytree;

import static org.tudalgo.algoutils.student.Student.crash;

$/**$

$*$ A class for checking the rules of a red$-$black tree.

$*/$

public class RBTreeChecker $\{$

$/**$

$*$ Checks if the given tree satisfies all the rules of a red$-$black tree.

$*$

$*$ @param rbTree the tree to check.

$*$ @throws RBTreeException if the tree does not satisfy any of the rules.

$*/$

public static void checkAllRules$($RBTree rbTree$)\{$

checkRule$1($rbTree$)$;

checkRule$2($rbTree$)$;

checkRule$3($rbTree$)$;

checkRule$4($rbTree$)$;

$\}$

$/**$

$*$ Checks if the given tree satisfies the first rule of black tree.

$*$

$*$ The first rule of a red$-$black tree states that every node is either red or black, i$.$e$.$ its color is not $\{$@code null$\}.$

$*$

$*$ @param rbTree the tree to check.

$*$ @throws RBTreeException if the tree does not satisfy the rule.

$*/$

public static void checkRule$1($RBTree rbTree$)\{$

$//$TODO: H$1$ a$)-$ remove if implemented

$\}$

$/**$

$*$ Checks if the given tree satisfies the second rule of black tree.

$*$

$*$ The second rule of a red$-$black tree states that the root of the tree is black.

$*$

$*$ @param rbTree the tree to check.

$*$ @throws RBTreeException if the tree does not satisfy the rule.

$*/$

public static void checkRule$2($RBTree rbTree$)\{$

crash$()$; $//$TODO: H$1$ b$)-$ remove if implemented

$\}$

$/**$

$*$ Checks if the given tree satisfies the third rule of black tree.

$*$

$*$ The third rule of a red$-$black tree states that no red node has a red child.

$*$

$*$ @param rbTree the tree to check.

$*$ @throws RBTreeException if the tree does not satisfy the rule.

$*/$

public static void checkRule$3($RBTree rbTree$)\{$

crash$()$; $//$TODO: H$1$ c$)-$ remove if implemented

$\}$

$/**$

$*$ Checks if the given tree satisfies the fourth rule of black tree.

$*$

$*$ The fourth rule of a red$-$black tree states that all paths from a node to a leave or half$-$leave contain the same number of black nodes.

$*$

$*$ @param rbTree the tree to check.

$*$ @throws RBTreeException if the tree does not satisfy the rule.

$*/$

public static void checkRule$4($RBTree rbTree$)\{$

crash$()$; $//$TODO: H$1$ a$)-$ remove if implemented

$\}$

$\}$