[#BloombergLP-bslalg-RbTreeUtil-validateRbTree-05]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/bslalg.adoc[bslalg]::xref:BloombergLP/bslalg/RbTreeUtil.adoc[RbTreeUtil]::validateRbTree
:relfileprefix: ../../../
:mrdocs:

Return the (common) number of black nodes on each path from the specified `rootNode` to a leaf in the tree, 0 if `rootNode` is 0, and a negative number if `rootNode` does not refer to a valid red&hyphen;black binary search tree, ordered according to the specified `comparator`&period; Optionally specify `errorNode` and `errorDescription` in which to load the address of a node violating a red&hyphen;black tree constraint and a description of that violation, respectively&period; The behavior is undefined unless `rootNode` is 0, or refers to a valid binary tree&period;

== Synopsis

Declared in `&lt;bslalg&lowbar;rbtreeutil&period;h&gt;`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template&lt;class NODE&lowbar;COMPARATOR&gt;
static
int
validateRbTree(
    xref:BloombergLP/bslalg/RbTreeNode.adoc[RbTreeNode] const* rootNode,
    NODE&lowbar;COMPARATOR const& comparator);
----

== Description

Each node of a red&hyphen;black tree is colored either red or black&semi; null nodes are considered black&period; Four requirements must be satisfied for `rootNode` to refer to a valid red&hyphen;black binary search tree&colon;

1&period; For each node in the tree, no descendents to the left of that node would order after that node (according to the `comparator`), and no descendents to the right of that node would order before it&period; 2&period; For each node in the tree, each non&hyphen;null child of that node refers to that node as its parent&period; 3&period; If a node in the tree is colored red, all its children are colored black or are null (which is considered black)&period; 4&period; For each node in the tree, every path from that node to a leaf contains the same number of black nodes, where null children are considered black leaf nodes&period;

The behavior is undefined unless `rootNode` is 0, or refers to a valid binary tree&period; Note that the implementation of this function is recursive and has linear complexity with respect to the number of nodes in `tree`, it is intended for debugging purposes only&period;


[.small]#Created with https://www.mrdocs.com[MrDocs]#
