Created
May 31, 2024 15:50
-
-
Save moreati/2345d8fee172b6db481a538a6349596f to your computer and use it in GitHub Desktop.
Calculate required layers of a tree for given number of leaf nodes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import math | |
def tree_layers_count(leaf_nodes_count: int, degree: int) -> int: | |
r""" | |
Return the number of layers required for a given number of leaf nodes, | |
if each node can have degree children & nodes are filled depth first. | |
E.g. to have 5 leaf nodes, a degree 4 tree requires 3 layers | |
* | |
_______________ _|_ _ | |
/ / \ \ | |
* * | |
_ _|_ _ _ _|_ _ | |
/ / \ \ / / \ \ | |
* * * * * | |
>>> tree_layers_count(0, degree=4) | |
0 | |
>>> tree_layers_count(1, degree=4) | |
1 | |
>>> [tree_layers_count(n, degree=4) for n in [2, 3, 4]] | |
[2, 2, 2] | |
>>> [tree_layers_count(n, degree=4) for n in [5, 10, 16]] | |
[3, 3, 3] | |
>>> [tree_layers_count(n, degree=4) for n in [17, 33, 64]] | |
[4, 4, 4] | |
>>> tree_layers_count(65, degree=4) | |
5 | |
""" | |
if leaf_nodes_count == 0: | |
return 0 | |
return math.ceil(math.log(leaf_nodes_count, degree)) + 1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment