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:

pattern001

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:

pattern002


 

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

bst1The 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.