Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be a counterexample?

Recall the following definitions.

Perfectly balanced node: A node of a binary tree is said to be perfectly balanced if the absolute difference in the number of vertices in its left subtree and its right subtree is atmost 1.

Perfectly Balanced Tree: A binary tree is called perfectly balanced if all its nodes are perfectly balanced.

Trivial Fact: The height of a perfectly balanced tree is $\Theta (\log n)$ where $n$ is the number of nodes in the tree.

  • 1
    $\begingroup$ You mean really perfectly balanced, where all levels of the tree are filled? Then you can colour all nodes black. $\endgroup$ – Hendrik Jan Aug 30 '19 at 0:24
  • $\begingroup$ @HendrikJan I've added the definition of perfectly balanced tree in the question. $\endgroup$ – Kaind Aug 30 '19 at 12:17
  • 1
    $\begingroup$ Any AVL-tree can be coloured Red-Black (the wikipedia page on Red-Black trees states this, without references). As your perfect balance is more strict than AVL-trees, that answers your question. I find it hard to locate explicit algorithms that do the colouring. One suggestion was given by Karolis here. $\endgroup$ – Hendrik Jan Aug 31 '19 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.