Implementation of a Family Tree with Traversal and Ancestor Finding

This assignment requires the development of a program to manage a family tree structure using a general tree. The program must store each family member's name and year of birth. Key functionalities include implementing recursive preorder and postorder traversals, as well as a breadth-first traversal. The core task involves finding common ancestors for specified pairs of family members, displaying them from most recent to least recent. The input is read from a file, detailing the tree structure and ancestor search queries. The output consists of the tree traversals and the identified common ancestors for each query. The program must handle edge cases, including empty trees, and adhere to specific input and output formats.

Fred, 1900
John, 1925 Joan, 1927
Mary, 1950 John, 1951 Fred, 1953 Susan, 1949 David, 1952
Jason, 1972 Heather, 1975
Michael, 2005
Adam, 1982Sarah, 1979Mark, 1977Amy, 1983
Hailey, 2005Sydney, 2002
Fred, 1980
The goal of this assignment is to practice manipulating and traversing trees.
You are to write a program that handles a family tree structure. Since there is no restriction on the number
of children that any person in the family has, the family tree must be a general tree. The family tree
structure keeps track of only one parent of each node (you can think of this as a “descendants view”, in
which we are interested only in showing the descendants of a given ancestor). Each node stores 2 pieces
of information: a name and a year of birth. Note that there are no restrictions on the number of family
members with the same name, or on the number of family members born in the same year; however, for
any given node, the year of birth must always be later than the year of birth of its parent.
You may assume that names are strings containing only upper- or lower-case alphabetic characters with
no white space. You may also assume that this is strictly a tree, i.e. it is connected and there are no cycles.
You must implement all of the following in your program:
 Recursive preorder traversal
 Recursive postorder traversal
 Breadth-first traversal (does not need to be recursive)
 For given names name1 and name2, find all common ancestors for every pair of nodes (n1,n2)
in which n1.name = name1 and n2.name = name2, from the most recent common ancestor to
the least recent common ancestor. In the case that n1 is an ancestor of n2, then n1 should also be
returned as an ancestor, and similarly for the case that n2 is an ancestor of n1. Hint: although it is
not a requirement, consider using a pair of stacks in your implementation.
Note that when printing the information for a given node, both name and year of birth must be printed.
Example:
In this example, there are three family members with the name “Fred” and two with the name “John”. If
we wish to find all common ancestors of “John” and “Fred”, then all of the following must be printed:
Common ancestors of (John, 1925) and (Fred, 1900):
(Fred, 1900)
Common ancestors of (John, 1925) and (Fred, 1953):
(John, 1925), (Fred, 1900)
Common ancestors of (John, 1925) and (Fred, 1980):
(Fred, 1900)
Common ancestors of (John, 1951) and (Fred, 1900):
(Fred, 1900)
Common ancestors of (John, 1951) and (Fred, 1953):
(John, 1925), (Fred, 1900)

Common ancestors of (John, 1951) and (Fred, 1980):
(Fred, 1900)
Input: Your program should read from a file; this file has the following format:
The name and year of birth for the root.
For each node in the tree (in preorder):
An integer value indicating that the node has n children
The name and year of birth of the 1st child
<Information for descendants of the 1st child, in preorder>
The name and year of birth of the 2nd child
<Information for descendants of the 2nd child, in preorder>
etc.
An integer value m, specifying the number of common ancestor checks desired.
A sequence of m lines, each containing 2 names for which we wish to find all common ancestors.
Important note: it is possible for the tree to be empty. In this case, either the file is completely empty, or
it starts with an integer (since you can assume that all names consist of alphabetical characters only). This
is a difficult case to handle but it will be allocated a small number of marks. You are advised to ensure
that your program works properly for non-empty trees first, since this will be worth far more marks.
Output: After creating the tree, the following steps should be performed:
 Print “Preorder traversal” and print the contents of the nodes, one per line, in preorder
 Print “Postorder traversal” and print the contents of the nodes, one per line, in postorder
 Print “Breadth-first traversal” and print the contents of the nodes, one per line, in breadth-first order
 For each pair of nodes matching each pair of names (name1, name2) print “Common ancestors of
(name1, year1) and (name2, year2):” followed by the list of common ancestors in the format
shown above.
.