Two binary trees are said to have the same shape if every pair of nodes in corresponding positions in the two trees are the roots of subtrees that have the same shape. Intuitively, two binary trees have the same shape if nodes in corresponding positions have the same kind of children. The data values in the corresponding nodes do not matter; only the nodes' positions relative to each other matter.
The input data consists of two lines of integers with one space between each two numbers. Write a program to construct a binary search tree using the integers on the first line and to construct a second binary search tree using the integers on the second line. Then, determine whether or not the two binary search trees have the same shape and print out one of the following messages:
The two trees have the same shape. The two trees have different shapes.
For example, if the input data consisted of the following two lines, your program should construct the BSTs below and display "The two trees have different shapes."
29 36 40 8 22 33
51 30 27 60 65 59
29 51
8 36 30 60
22 33 40 27 59 65
However, if the input data consisted of the following two lines, your program should construct the BSTs below and display "The two trees have the same shape."
71 90 75 25 80 60 87
30 10 60 31 40 50 20
71 30
25 90 10 60
60 75 20 31
80 40
87 50