Some of these questions use the following type Node, which
is the same as the Node type used in class.
struct Node
{
int item;
Node* left;
Node* right;
node(int i, Node* L, Node* R)
{
item = i;
left = L;
right = R;
}
};
Variable t has type Node*. You would like to make t point to a leaf that holds only item 25. Write a statement that accomplishes that. (A leaf is a node both of whose subtrees are empty.)
Write a function that takes a tree t (given by a pointer to its root) and returns the sum of all of the numbers in tree t. The sum of an empty tree is 0.
Write a function that writes all of the numbers in a binary search tree in ascending order on the standard output, one number per line. The function takes a parameter of type const Node*, pointing to the tree, and has a void return type.
The left-height of a tree is the number of nodes on the path in t that starts at the root and only follows left pointers until the left pointer is NULL. All of the nodes are counted, including the root and the node whose left pointer is NULL. By definition, the left-height of an empty tree is 0.
Write a function that takes a tree t, given as a pointer to the root (or NULL), and returns the left-height of tree t.
Write a function that takes a tree t and returns a new tree that has the same structure as t, but whose items are doubles of the items in tree t. For example, a node containing 8 in tree t has a corresponding node holding 16 in the new tree. This function is nondestructive; it does not change tree t.
Write a function that takes a tree t and changes all of the nodes in t, replacing each number by a number twice as large. For example, a node that previously contained 8 will end up containing 16. This function is destructive; it changes the tree.
If you insert 62 into the following binary search tree, using the basic algorithm that does not rebalance, what tree do you get?
If you insert 26 into the following binary search tree, without rebalancing, what tree do you get?
The height of a tree is the number of nodes on the longest path from the tree's root to a leaf. An empty tree is defined to have height 0.
A tree is full if (1) all of its leaves have the same height, and (2) all nonleaves have two nonempty subtrees. By definition, an empty tree is full.
Write a function that takes a tree t, given by a pointer to its root, and returns the height of tree t if t is full, but returns -1 if tree t is not full.
Using your function from the previous exercise, write a function that takes tree t and returns true if t is complete, false if t is not complete.