# Practice questions on recursion and binary trees

**Problem 1**: Examine the following pattern of asterisks and blanks, and write a recursive function that can generate exactly this pattern:

Generalize your solution to take N as input, and produce the above pattern of any size. N must be a power of 2 to generate a valid pattern.

The above snapshot is taken with N = 8. With N=4, the output would be as follows:

**Problem 2**: Given a binary search tree, print the elements in a *new* order, as suggested by the example shown below:

The expected output is: 10, 14, 2, 12, 25, 75, 8, 50, 15.

**Sample output**:

Printing the tree in reverse level order:

10 14 2 12 25 75 8 50 15

Dotty output in tree_output.dot:

digraph{

15 -> 8

8 -> 2

NULL0[shape=point]

2 -> NULL0

NULL1[shape=point]

2 -> NULL1

8 -> 12

12 -> 10

NULL2[shape=point]

10 -> NULL2

NULL3[shape=point]

10 -> NULL3

12 -> 14

NULL4[shape=point]

14 -> NULL4

NULL5[shape=point]

14 -> NULL5

15 -> 50

50 -> 25

NULL6[shape=point]

25 -> NULL6

NULL7[shape=point]

25 -> NULL7

50 -> 75

NULL8[shape=point]

75 -> NULL8

NULL9[shape=point]

75 -> NULL9

}

Copy and paste the above output into the dotty layout tool and click on “Make me a graph” in order to visualize the graph.

Alternatively, you could also execute “dotty tree_output.dot” from your unix shell, provided you have the native DISPLAY support.