Skip to content

Instantly share code, notes, and snippets.

@moreati
Created May 31, 2024 15:50
Show Gist options
  • Save moreati/2345d8fee172b6db481a538a6349596f to your computer and use it in GitHub Desktop.
Save moreati/2345d8fee172b6db481a538a6349596f to your computer and use it in GitHub Desktop.
Calculate required layers of a tree for given number of leaf nodes
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