Is a binary tree a red-black tree? algorithm puzzle

Red black trees are quite widely used.

A red black tree is a binary search tree, but with some additional colour constraints on the nodes (swiped from the wiki page).

• Each node is coloured either red or black.
• The root is coloured black.
• All NULL nodes are coloured black.
• Every red coloured node must have two black children.
• Every path from a given node to any of it's descendant NULL nodes must have the same number of black nodes.

These constraints ensure that the height of a red black tree on $n$ nodes is $O(\log n)$, and these constraints can be enforced during insertion and deletion, thus making insert/delete/search operations $O(\log n)$ each.

Now for the puzzle.

Suppose you are given a binary tree on $n$ nodes, without any colours on it. Can you determine if there is a red-black colouring of the nodes, which follows the above constraints? i.e. is the binary tree actually a red-black tree?

An $O(n)$ time algorithm is possible, but $O(n \log n)$ is ok too.

[Solution]