CompleteKaryTree

The full (perfect) $k$-ary tree of the given depth — every level completely filled.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageCompleteKaryTree✓↗

CompleteKaryTree(levels)binary ($k = 2$); levels is a LEVEL count, not a vertex count.

CompleteKaryTree(levels, k)$n = (k^{\text{levels}} - 1) / (k - 1)$ vertices, 1-indexed heap layout — vertex $i$'s children are $k(i-1)+2, \dots, k(i-1)+k+1$.

SageMathenumeratio_graph(graphs.BalancedTree(k, levels - 1))

Typed signatures

Type	Package	Applies
(integer, integer?) -> value	combinatorics	always

Domain: Collections

Details

• levels counts LEVELS, not vertices (kernel-verified): CompleteKaryTree(1, 2) is a single vertex, CompleteKaryTree(3, 2) has 7.

Examples

3 more kept as data, checked against the oracles

Basic #

1 + 2 + 4 = 7

live ↗

In$\mathrm{VertexCount}(\mathrm{CompleteKaryTree}(3, 2))$Out$7$

live ↗

In$\mathrm{VertexCount}(\mathrm{CompleteKaryTree}(1, 2))$Out$1$

A complete k-ary tree is always a tree ($n - 1$ edges, connected)

live ↗

In$\mathrm{IsTreeGraph}(\mathrm{CompleteKaryTree}(3, 2))$Out$\mathrm{True}$

The root of a 3-level ternary tree has 3 children

live ↗

In$\mathrm{VertexDegree}(\mathrm{CompleteKaryTree}(3, 3), 1)$Out$3$

Default is binary: 5 levels hold 31 vertices

live ↗

In$\mathrm{CompleteKaryTree}(5)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(3, 6), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(4, 9), \mathrm{UndirectedEdge}(5, 10), \mathrm{UndirectedEdge}(5, 11), \mathrm{UndirectedEdge}(6, 12), \mathrm{UndirectedEdge}(6, 13), \mathrm{UndirectedEdge}(7, 14), \mathrm{UndirectedEdge}(7, 15), \mathrm{UndirectedEdge}(8, 16), \mathrm{UndirectedEdge}(8, 17), \mathrm{UndirectedEdge}(9, 18), \mathrm{UndirectedEdge}(9, 19), \mathrm{UndirectedEdge}(10, 20), \mathrm{UndirectedEdge}(10, 21), \mathrm{UndirectedEdge}(11, 22), \mathrm{UndirectedEdge}(11, 23), \mathrm{UndirectedEdge}(12, 24), \mathrm{UndirectedEdge}(12, 25), \mathrm{UndirectedEdge}(13, 26), \mathrm{UndirectedEdge}(13, 27), \mathrm{UndirectedEdge}(14, 28), \mathrm{UndirectedEdge}(14, 29), \mathrm{UndirectedEdge}(15, 30), \mathrm{UndirectedEdge}(15, 31)\bigr\rbrack)$

Three levels with branching 3 give 13 vertices

live ↗

In$\mathrm{CompleteKaryTree}(3, 3)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(2, 7), \mathrm{UndirectedEdge}(3, 8), \mathrm{UndirectedEdge}(3, 9), \mathrm{UndirectedEdge}(3, 10), \mathrm{UndirectedEdge}(4, 11), \mathrm{UndirectedEdge}(4, 12), \mathrm{UndirectedEdge}(4, 13)\bigr\rbrack)$

Scope #

Two levels of ternary branching: a root with 3 leaves

live ↗

In$\mathrm{CompleteKaryTree}(2, 3)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4)\bigr\rbrack)$

Applications #

Eccentricity grows from the root's 2 to 4 at the leaves

live ↗

In$\mathrm{Map}(\operatorname{\_1}↦\mathrm{VertexEccentricity}(\mathrm{CompleteKaryTree}(3, 2), \operatorname{\_1}), \mathrm{VertexList}(\mathrm{CompleteKaryTree}(3, 2)))$Out$\bigl\lbrack2, 3, 3, 4, 4, 4, 4\bigr\rbrack$

Properties #

Trees are bipartite

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{CompleteKaryTree}(3, 3))$Out$\mathrm{True}$

A tree has no cycles

live ↗

In$\mathrm{IsAcyclicGraph}(\mathrm{CompleteKaryTree}(3, 3))$Out$\mathrm{True}$

No vertex is joined to itself

live ↗

In$\mathrm{IsLoopFreeGraph}(\mathrm{CompleteKaryTree}(3, 3))$Out$\mathrm{True}$

Three levels of 4-ary branching: $1+4+16=21$ vertices

live ↗

In$\mathrm{CompleteKaryTree}(3, 4)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(2, 7), \mathrm{UndirectedEdge}(2, 8), \mathrm{UndirectedEdge}(2, 9), \mathrm{UndirectedEdge}(3, 10), \mathrm{UndirectedEdge}(3, 11), \mathrm{UndirectedEdge}(3, 12), \mathrm{UndirectedEdge}(3, 13), \mathrm{UndirectedEdge}(4, 14), \mathrm{UndirectedEdge}(4, 15), \mathrm{UndirectedEdge}(4, 16), \mathrm{UndirectedEdge}(4, 17), \mathrm{UndirectedEdge}(5, 18), \mathrm{UndirectedEdge}(5, 19), \mathrm{UndirectedEdge}(5, 20), \mathrm{UndirectedEdge}(5, 21)\bigr\rbrack)$

About

Examples	15
Checked against	Wolfram Language 15 agreeSageMath 8 agree3 differ
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: StarGraph, IsTreeGraph