These problems use the following type, Node.
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.
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.
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 complete if (1) all of its leaves have the same height, and (2) all nonleaves have two nonempty subtrees. By definition, an empty tree is complete.
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 complete, but returns -1 if tree t is not complete.
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.
A node in a tree is height-balanced if the heights of its two subtrees differ by no more than 1. That is, if the left subtree has height h and the right subtree has height g, then the node is height balanced if |h-g| <= 1.
An entire tree is height-balanced if all of its nodes are height-balanced. By definition, an empty tree is height-balanced.
Write a function that takes a parameter t that is a tree (a pointer to the root, or NULL), and returns the height of t if t is height balanced, but returns -1 if t is not height-balanced.
Write a function that takes a parameter t that is a tree (a pointer to the root, or NULL), and returns true if t is height balanced, false if t is not height-balanced.