Red-Black trees are commonly used self balancing binary trees. Another example of a self balancing binary trees is an AVL tree.
A common interview question is to determine if a given binary tree is an AVL tree, based on the height constraints an AVL tree has.
A red-black tree has colouring constraints (check the wiki page above), where each node is coloured either red or black and then there are some constraints based on the colours.
The puzzle here is to determine if a given binary tree of $n$ nodes can be coloured [i.e. each node coloured red or black] so as to satisfy the constraints of a red-black tree.
Can you give an algorithm which runs in $O(n)$ time?
[Solution]
A common interview question is to determine if a given binary tree is an AVL tree, based on the height constraints an AVL tree has.
A red-black tree has colouring constraints (check the wiki page above), where each node is coloured either red or black and then there are some constraints based on the colours.
The puzzle here is to determine if a given binary tree of $n$ nodes can be coloured [i.e. each node coloured red or black] so as to satisfy the constraints of a red-black tree.
Can you give an algorithm which runs in $O(n)$ time?
[Solution]
No comments:
Post a Comment