A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to…