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.

💡TIP

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!

🏁MISSION

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)

📖ARTICLE

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.

👩‍💻CODE SHOT

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! ⤵