Skip to main content
Code Golf

Return to Question

Fixed 1 grammatical error and 1 spelling error
Source Link
R. Kap
R. Kap
  • 4.9k
  • 2
  • 15
  • 37

As a programmer or computer scientist one might encounter quite a lot of trees - of course not the woody growing-in-the-wrong-direction kind, but the nice, pure mathematical kind:

  • size: The number of nodes in the tree.
  • depth: The number of edges on the longest path from the root to any leaf.
  • breadth: The number of leafsleaves.
  • degree: The maximum number of child nodes for any node.

As a programmer or computer scientist one might encounter quite a lot of trees - of course not the woody growing-in-the-wrong-direction kind, but the nice pure mathematical kind:

  • size: The number of nodes in the tree.
  • depth: The number of edges on the longest path from the root to any leaf.
  • breadth: The number of leafs.
  • degree: The maximum number of child nodes for any node.

As a programmer or computer scientist one might encounter quite a lot of trees - of course not the woody growing-in-the-wrong-direction kind, but the nice, pure mathematical kind:

  • size: The number of nodes in the tree.
  • depth: The number of edges on the longest path from the root to any leaf.
  • breadth: The number of leaves.
  • degree: The maximum number of child nodes for any node.
subroutine clarification
Source Link
Laikoni
Laikoni
  • 26.3k
  • 6
  • 52
  • 115

You have to submit a program or function for each of the tools, however they might share subroutines (e.g. parsing) which then have to be submitted only once. Note that those subroutines need to be full programs or functions too.

You have to submit a program or function for each of the tools, however they might share subroutines (e.g. parsing) which then have to be submitted only once.

You have to submit a program or function for each of the tools, however they might share subroutines (e.g. parsing) which then have to be submitted only once. Note that those subroutines need to be full programs or functions too.

Source Link
Laikoni
Laikoni
  • 26.3k
  • 6
  • 52
  • 115

Show off your tree analysing toolbox

As a programmer or computer scientist one might encounter quite a lot of trees - of course not the woody growing-in-the-wrong-direction kind, but the nice pure mathematical kind:

  *<- root (also a node)
 /|\<- edge
* * *<- inner node
|  / \
* *   *<- leaf (also a node)
  |
  *

Naturally over time we all have put together our own small handy toolbox to analyse such trees as we encounter them, right? Now is the time to show it off!

Task

The toolbox must include the following functions:

  • size: The number of nodes in the tree.
  • depth: The number of edges on the longest path from the root to any leaf.
  • breadth: The number of leafs.
  • degree: The maximum number of child nodes for any node.

You have to submit a program or function for each of the tools, however they might share subroutines (e.g. parsing) which then have to be submitted only once.

Input Format

The trees can be given in any reasonable format capturing the structure, e.g. the tree

  *
 / \
*   *

could be represented through parentheses (()()), lists of lists [[],[]], or data structures with a constructor T[T[],T[]]. However not through linearisation [2,0,0] or a format like (size, depth, breath, degree, whatever-else-is-needed-to-make-this-format-unique-for-every-tree). Generally speaking, your tree format should not contain numbers.

Output Format

A natural number for each of the properties described above.

Scoring

Lowest code in bytes for the 4 functions in every language wins, thus I will not accept an answer.

Feel free to provide additional tree tools like fold, isBinaryTree, preLinearise, postLinearize, or whatever you like. Of course those don't have to be included in the byte count.

Examples

First the tree is given in the sample formats from above, then the results of the functions as (size, depth, breadth, degree).

()
[]
T[]
(1,0,1,0)

(()())
[[],[]]
T[T[],T[]]
(3,1,2,2)

((())()((())()))
[[[]],[],[[[]],[]]]
T[T[T[]],T[],T[T[T[]],T[]]]
(8,3,4,3)

((()())((())()((())()))(()())(()))
[[[],[]],[[[]],[],[[[]],[]]],[[],[]],[[]]]
T[T[T[],T[]],T[T[T[]],T[],T[T[T[]],T[]]],T[T[],T[]],T[T[]]]
(17,4,9,4)

((((((((()))))))))
[[[[[[[[[]]]]]]]]]
T[T[T[T[T[T[T[T[T[]]]]]]]]]
(9,8,1,1)

(((((((()()))((()()))))((((()()))((()()))))))((((((()()))((()()))))((((()()))((()())))))))
[[[[[[[[],[]]],[[[],[]]]]],[[[[[],[]]],[[[],[]]]]]]],[[[[[[[],[]]],[[[],[]]]]],[[[[[],[]]],[[[],[]]]]]]]]
T[T[T[T[T[T[T[T[],T[]]],T[T[T[],T[]]]]],T[T[T[T[T[],T[]]],T[T[T[],T[]]]]]]],T[T[T[T[T[T[T[],T[]]],T[T[T[],T[]]]]],T[T[T[T[T[],T[]]],T[T[T[],T[]]]]]]]]
(45,7,16,2)