This second challenge, based upon simple concepts such as encoding and decoding information, will also test how you deal with the psychological horror of the unknown (and possibly, the unknowable) 😉 You are allowed to use any language, unless the challenge specifies a specific language that you are to use. Post your source code, compiler version, and OS as a comment.
Some definitions:
a) The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.
b) A leaf node has no children.
c) The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.
d) A binary tree is a tree data structure in which each node has at most two children.
Requirements:
1) A function named f1 , which will take a rooted binary tree structure and encodes the binary tree structure and its values into a single dimension array, which is then returned.
2) A function named f2, which will take single dimension array (encoded by f1) and converts the array into a binary tree structure, which is then returned.
3) A function named f3, that will return a randomly generated rooted binary tree structure, such that the binary tree structure has:
3a) One root node
3b) Every node, other than a leaf node, will have randomly, one or two children
3c) Each node, including the root and leaf nodes, will randomly contain one of the following values: 1,2,3,5,7
3d) The height of the tree is greater than zero and less than six.
Challenge:
Write a program that uses the output of f3 as input into f1, which is then used as input into f2.
Your program must show that the output of f2, its structure and the values of each node, matches the output of f3.
Language: Any
Difficulty: In the Mouth of Madness