Write an inorder, preorder, and postorder traversal of the following tree.
36
/ \
23 42
/ \ / \
13 29 40 46
\ \
17 50
\
19
Write a function that prints the postorder traversal of a binary tree given a preorder and inorder traversal of the tree. This function need not actually construct the tree, just print it. Its prototype will be
void printPostOrder(int *inorder, int *preorder, int num_nodes);(You'll want to use recursion for this.)
(Problem communicated to me by Sridhar Radhakrishnan.)
Say we implement a 2-3 tree using the below structure. How can you implement TwoThreeNode::search() recursively?
class TwoThreeNode {
public:
bool search(int k); // return true if key k is in the tree
private:
int num_keys; // 1 if 1 key (2 subtrees), 2 if 2 keys (3 subtrees)
int key[2]; // key[1] is undefined if num_keys == 1
TwoThreeNode *child[3];
// child[0] is the left child, child[2] is the right child,
// and child[1] is the middle child if the node has 2 keys
// (otherwise it is undefined).
};
Bound the number of comparisons for searching in a 2-3 tree. Do not use big-O notation.
For each of the following, say whether the tree is an AVL tree. If not, say why not.
4
/ \
2 8
/ \
0 10
\
11
4
/ \
2 8
/ / \
0 3 10
4
/ \
2 8
/ / \
0 7 10
\
11
4
/ \
2 8
/ /|\
0 3 9 10
Rotate the edge between 8 and 10 in the following tree.
4
/ \
2 8
/ / \
0 7 10
\
11
What single rotation can we perform on the following to make it into an AVL tree?
4
/ \
2 8
/ / \
0 7 10
\
11
\
15
Say we have the following binary search tree class.
class BinarySearchTree {
public:
bool isAVL();
int height(); // returns the subtree's height (a leaf has height 1)
private:
int key;
BinarySearchTree *left;
BinarySearchTree *right;
};
Write BinarySearchTree::isAVL(), which returns true if the tree
satisfies the AVL property. Assume that the tree is a valid binary
search tree.
Create a trie from the following.
va2a km3u anandr cmb cld schatz slease ub23 jeremyw crossman grandhi schwartz echen vieta