KaryTree

The k-ary tree on n vertices, in breadth-first (heap) layout — sized by vertex count, not depth.

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

KaryTree(n)the binary (k = 2) tree on n vertices

KaryTree(n, k)the k-ary tree on n vertices

Typed signatures

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

Domain: Collections

Details

• Vertex i's parent is ⌊(i - 2) / k⌋ + 1 — the same heap layout CompleteKaryTree uses, but sized by VERTEX COUNT rather than level count, so the last level need not be full.
• NOT the same thing as our FullKAryTrees DOMAIN (the combinatorial family of every n-node full k-ary tree shape, for ranking/enumeration) or CompleteKaryTree (a LEVEL count, always perfectly filled) — three different heads that happen to share a name fragment.

Examples

Basic #

live ↗

In$\mathrm{KaryTree}(7, 2)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7\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)\bigr\rbrack)$

A binary tree on ten vertices, filled level by level

live ↗

In$\mathrm{KaryTree}(10)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10\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)\bigr\rbrack)$

Ternary with fifteen vertices, so the last level is partly filled

live ↗

In$\mathrm{KaryTree}(15, 3)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\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), \mathrm{UndirectedEdge}(5, 14), \mathrm{UndirectedEdge}(5, 15)\bigr\rbrack)$

Scope #

The default k = 2, the same binary tree KaryTree(5, 2) builds

live ↗

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

The default arity is two

live ↗

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

With three children per node, four vertices make a star

live ↗

In$\mathrm{KaryTree}(4, 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 with depth: the root is closest to everything

live ↗

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

Properties #

Every tree is bipartite, split by level parity

live ↗

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

A tree has no cycles

live ↗

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

No vertex is joined to itself

live ↗

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

Eight vertices with four children per node: the root and its four children, then three more below

live ↗

In$\mathrm{KaryTree}(8, 4)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8\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)\bigr\rbrack)$

About

Examples	11
Checked against	Wolfram Language 11 agree
Crosswalk	Wolfram Language

See also: CompleteKaryTree