Red-Black Tree Black Height

Problem

Verify the black height of a binary tree. colors[i] is "R" or "B" and children[i] = [left, right] with -1 for an absent child. Every path from the root to a null child must contain the same number of black nodes; return that count (excluding the null child), or -1 when the paths disagree or the root is not black. An empty tree has black height 0.

Hint

Recursively return each subtree's black height, or -1 as soon as two paths disagree.

Test cases

case 1

in: [["B"],[[-1,-1]]]

expected: 1

case 2

in: [["B","R"],[[-1,1],[-1,-1]]]

expected: 1

case 3

in: [["B","R","R","B","B","B","B"],[[1,2],[3,4],[5,6],[-1,-1],[-1,-1],[-1,-1],[-1,-1]]]

expected: 2

case 4

in: [["R","B"],[[1,-1],[-1,-1]]]

expected: -1

case 5

in: [["B","B"],[[1,-1],[-1,-1]]]

expected: -1

Starter codePython

def rb_black_height(colors, children):
    # Your code here
    pass

5 test cases · run your code against them in the editor