[#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‐black binary search tree, ordered according to the specified `comparator`. Optionally specify `errorNode` and `errorDescription` in which to load the address of a node violating a red‐black tree constraint and a description of that violation, respectively. The behavior is undefined unless `rootNode` is 0, or refers to a valid binary tree.

== Synopsis

Declared in `<bslalg_rbtreeutil.h>`

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

== Description

Each node of a red‐black tree is colored either red or black; null nodes are considered black. Four requirements must be satisfied for `rootNode` to refer to a valid red‐black binary search tree:

1. 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. 2. For each node in the tree, each non‐null child of that node refers to that node as its parent. 3. If a node in the tree is colored red, all its children are colored black or are null (which is considered black). 4. 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.

The behavior is undefined unless `rootNode` is 0, or refers to a valid binary tree. 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.


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