CPS 100, Fall 2003, Written Trees
35 points
due October 27 at 11:59pm
These problems provide practice with trees, recursion, and big-Oh.
You can talk about the problems with up other people, but each person
should submit his/her own version of the solutions. This means
your writeups should be your own work, even if you talk with
other people. It's in your own interest to do your own work
as test questions will be difficult if you cannot do these questions.
You should submit a file whose name must be tree.cpp, and a
README file that indicates how long you spent on these problems and with
whom you consulted.
You are to submit solutions to these problems using
submit_cps100 writtentree tree.cpp README
The solutions are in the file tree.cpp so that you can have your code
formatted automatically (e.g., if you use emacs). You should NOT make
your solutions run, you're just typing solutions to make them easier
to read and to allow for electronic submission.
It is important to think about your answers, not to run them.
Assume the following declarations have been made
struct TreeNode
{
string info;
TreeNode * left;
TreeNode * right;
TreeNode * parent;
TreeNode (int val, TreeNode * lt, TreeNode * rt, TreeNode * p)
: info(val), left(lt), right(rt), parent(p)
{ }
};
- Binary Search Tree Iterator
- Write functions that return the Minimum and Maximum node
from a tree rooted at t. Give the average-case big-Oh
for each.
TreeNode* Minimum(TreeNode * t)
// pre: t points to possibly empty BST
// post: returns pointer to node with minimum key (NULL if t is empty)
TreeNode* Maximum(TreeNode * t)
// pre: t points to possibly empty BST
// post: returns pointer to node with maximum key (NULL if t is empty)
- Write a function to find the inorder Successor of a node. You
probably should use the parent link and the
Minimum function you wrote earlier.
TreeNode* Successor(TreeNode * t)
// pre: t points to possibly empty BST
// post: returns next node in inorder traversal of tree, returns NULL if
// there are no more nodes left
- What is the big-Oh (worst case) of your solution. Justify with either a recurrence
relation or analysis of the number of steps if iterative.
- The following is an inorder traversal of a tree from the root
void InorderTraversal(TreeNode *root)
{
for (TreeNode *t = Minimum(root); t != NULL; t = Successor(t))
cout << t->info << endl;
}
What is the big-Oh of InorderTraversal (worst case)? Justify your answer.
- Enumerating Binary Trees
There is one binary tree with one node. There
are two differently shaped trees with two nodes.
There are 14 different (shaped) binary trees
with four nodes. These different trees are shown below.
- Draw all five of the different binary trees with three nodes.
- Using the information about how many trees there are with
1, 2, 3, and 4 nodes determine how many different binary trees
there are with 5 nodes. Do not draw them, but reason
about how many there must be based on:
- There is a root node.
- There are four other nodes that are distributed between
the left and right subtrees.
For example, there must be 28 different five-node trees in which all the
nodes but the root are either in the left subtree or all in the right
subtree (why?)
In the next three problems assume trees store int values rather
than string values
- isBST?
- Suppose you have helper functions Minimum and
Maximum that return the min or max node from a non-empty tree as
in problem 1. Write an isBST function that returns true if a tree is a
binary search tree and false otherwise. Use the helper functions, and don't
forget to check every node in the tree. Your solution will likely not be
very efficient (i.e. > O(n) time), but give the recurrence for your solution (average case).
- The solution above runs slowly since it traverses
over some parts of the tree many times. A better solution looks at each node
only once. The trick is to write a utility helper function isBSTRecur(TreeNode* t, int min, int max) that traverses down the tree keeping track of the
narrowing min and max allowed values as it goes, looking at each node only once.
The initial values for min and max should be INT_MIN and
INT_MAX. The bounds will narrow
from there.
Write IsBSTRecur and give its recurrence.
int IsBST2(TreeNode* root)
// post: Returns true if the given tree is a binary search tree
// (efficient version)
{
return IsBSTRecur(root, INT_MIN, INT_MAX));
}
int IsBSTRecur(TreeNode* node, int min, int max)
// post: Returns true if the given tree is a BST aAND its
// values are >= min and <= max.
{
- FindKthInOrder
-
Write the function FindKthInOrder whose header is given below.
Given an integer k and a binary search tree with unique values,
FindKthInOrder returns a pointer to the node that contains the
kth element if the elements are in sorted order --- the smallest value
is k == 1, the second smallest is k == 2, and so on.
For example, in the tree t shown below (t points to the root),
FindKthInOrder(t,4) returns a pointer to the node with value 9,
FindKthInOrder(t,8) returns a pointer to the node with value 18,
and FindKthInOrder(t,12) returns NULL since there are only 9 nodes
in the tree.
You may find it useful to call the function count discussed
in lecture that returns the number of nodes in a tree.
int count(TreeNode * t)
// post: returns # nodes in t
{
if (t == 0) return 0;
return 1 + count(t->left) + count(t->right);
}
TreeNode * FindKthInOrder(TreeNode * t, int k)
// pre: t is a binary search tree with unique values
// post: returns pointer to the kth node in sorted order,
// returns NULL if t has fewer than k nodes.
-
Assuming trees are roughly balanced (e.g., average case), write a
recurrence for your solution to FindKthInOrder and give the
solution to the recurrence.
- Write a recurrence for your solution to FindKthInOrder
for the worst case, i.e., when a tree is completely unbalanced
and the function is called to do the most work on every recursive call.
What is the solution to this recurrence?
- hasPathSum
Write the function hasPathSum whose header is given below.
hasPathSum returns true if there exists some root-to-leaf
path in the tree whose root is t whose nodes sum to
target and returns false otherwise.
For example, in the tree shown below there are exactly four
root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18.
Thus the value of hasPathSum(t,27) should be true and the
value of hasPathSum(t,30) should be false (assuming
t points to the root of the tree --- the node whose info
field has value 5.)
Hint: You should make two recursive calls, you must decide on the value
of target for each recursive call so that you can use the return
values of the recursive calls to solve the problem. Note: in a tree
with one node (a leaf) you can determine immediately if there's a path
that sums to the target based on whether the target and the node are equal.
bool hasPathSum(TreeNode * t, int target)
// post: returns true iff t has a root-to-leaf path
// that sums to target
- Diameter
Recall from recitation the
Diameter of a tree (sometimes called the width) is the number
of nodes on the longest path between two leaves in the tree. The
diagram below shows two trees each with diameter nine, the leaves that
form the ends of a longest path are shaded (note that there is more
than one path in each tree of length nine, but no path longer than
nine nodes).
It can be shown that the diameter of a tree T is the largest
of the following quantities:
- the diameter of T's left subtree
- the diameter of T's right subtree
- the longest path between leaves that goes through the root of T
(this can be computed from the heights of the subtrees of T)
Here's code that's almost a direct translation of the three properties
above (assuming the existence of a standard O(1) max function that
returns the larger of two values).
int diameter(TreeNode * t)
// post: returns diameter of t
{
if (t == 0) return 0;
int leftD = diameter(t->left);
int rightD = diameter(t->right);
int rootD = height(t->left) + height(t->right) + 1;
return max(rootD, max(leftD, rightD));
}
-
However, the function as written does not run in O(n) time.
Write a recurrence for this implementation and what the solution
to the recurrence is. Assume trees are roughly balanced in writing
the recurrence.
- Write a version of diameter that runs in O(n) time.
Your function should use an auxiliary/helper function as described
below. The helper function should make
two recursive calls and do O(1) other work.
int diameterHelper (TreeNode * t, int & height)
// pre: t is a binary tree
// post: return (via reference param) height = height of t
// return as value of function: diameter of t
{
// write this
}
int diameter(TreeNode * t)
// post: returns diameter of t
{
int height;
return diameterHelper(t, height);
}
- Isomorphic Trees
- Two binary trees s and t are isomorphic if
they have the same shape; the values stored in the nodes do not affect
whether two trees are isomorphic. In the diagram below, the tree in
the middle is not isomorphic to the other trees, but the tree
on the right is isomorphic to the tree on the left.
Write a function isIsomorphic that returns true if its two
tree parameters are isomorphic and false otherwise. You must also
give the big-Oh running time (in the average case, assuming each tree
is roughly balanced) of your function with a justification.
Express
the running time in terms of the number of nodes in trees s
and t combined, i.e., assume there are n nodes together
in s and t with half the nodes in each tree.
bool isIsomorphic(TreeNode * s, TreeNode * t)
// post: returns true if s is isomorphic to t, else returns false
-
Two trees s and t are quasi-isomorphic if
s can be transformed into t by swapping left and
right children of some of the nodes of s. The values in the
nodes are not important in determining quasi-isomorphism, only the
shape is important. The trees below are quasi-isomorphic because if
the children of the nodes A, B, and G in the tree on the left are
swapped, the tree on the right is obtained.
Write a function isQuasiIsomorphic that returns true if two
trees are quasi-isomorphic. You must also give the big-Oh running
time (in the average case, assuming each tree is roughly balanced) of
your function with a justification. Express the running time in terms
of the number of nodes in trees s and t combined as
with the previous problem.
bool isQuasiIsomorphic(TreeNode * s, TreeNode * t)
// post: returns true if s is quasi-isomorphic to t, else returns false
Jeff Forbes
Last modified: Tue Nov 11 16:35:30 EST 2003