• Get To Know Calkin–Wilf Tree And Learn About Time Complexity Of Data Structures

Hello, checkiomates🐱‍👤!

This week we offer you to investigate the Calkin–Wilf tree and find specific branch using knowledge about time complexity of data structures.


We allow users to assign hotkeys to "Run Code", "Check Solution" and stop code. You may see current combinations on buttons and change them in editor menu. If you want to discover all CheckiO features, visit our tutorial. It's a longread, but it's worth it!


Exploring Calkin-Wilf Tree by freeman_lex -

The nodes of the Calkin–Wilf tree, when read in level order so that the elements in each level are read from left to right, produce the linear sequence of all possible positive rational numbers. Almost as if by magic, this construction guarantees every positive integer fraction to appear exactly once in this sequence. Even more delightfully, this construction makes every rational number to make its appearance in its lowest reduced form!

The tree is rooted at the number 1 (1/1), and any rational number expressed in simplest terms as the fraction a/b has as its two children the numbers a/(a + b) and (a + b)/b. Your function should return the n:th element of this sequence.

calkin_wilf(2) == (1, 2)
calkin_wilf(3) == (2, 1)
calkin_wilf(10) == (3, 5)


Python Big O: the time complexities of different data structures in Python -

This article is primarily meant to act as a Python time complexity cheat sheet for those who already understand what time complexity is and how the time complexity of an operation might affect your code. For a more thorough explanation of time complexity see Ned Batchelder's article/talk on this subject.


How do you think, what the following code does?

from collections.abc import Iterable

def ????????(items: list[int]) -> Iterable[int]:

    others = sorted(filter(bool, items))

    return (i and others.pop(0) for i in items)

🙌 Thanks for your attention! Hope to meet you at CheckiO. We are really interested in your thoughts! Please, leave a comment below! ⤵

Welcome to CheckiO - games for coders where you can improve your codings skills.

The main idea behind these games is to give you the opportunity to learn by exchanging experience with the rest of the community. Every day we are trying to find interesting solutions for you to help you become a better coder.

Join the Game