Trees Practice Problems

Beginner Problems

1. Write a program that finds the height of a binary tree.
2. Write a program that counts the number of nodes in a binary tree and the number of leaf nodes in a binary tree.
3. Given a binary tree, create another binary tree that is a mirror image of the given tree.
4. Write a program that implements the non-recursive form of the functions inorder(), preorder(), and postorder().
5. Write a program that maintains a dictionary of words as a binary tree.
6. Given any number, find whether that number is present in the binary tree. If present then find the level at which it is present.
7. Given two binary trees, write a program that finds whether the two binary trees are similar.
8. Write a program that finds the mirror images of each other.
9. Write a program that finds the number of nodes in a binary tree at each level.
10. Write a program that traverses a binary tree level by level, from left to right.
11. Write a function to insert a node t as a left child of any node s in a threaded binary tree.
12. Construct a BST: Construct a BST by inserting the following sequence of numbers:

    36, 26, 46, 21, 31, 41, 56, 11, 24, 51, 66

13. Using the BST you just created:
    • Show the steps to search for the number 41.
    • Delete the node with the value 21 (a node with two children).
    • Delete the node with the value 56 (a node with one child).
    • Delete the node with the value 11 (a leaf node).
14. How do you find the minimum and maximum element in a BST? Write the algorithms.
15. Write a recursive C function to search for a given key in a BST.
16. Write an iterative C function to insert a new node into a BST.

Expression Trees

1. What is an Expression Tree? What do the leaf nodes and internal nodes represent?
2. Construct an expression tree for the infix expression:

   ((A + B) * (C - D))

3. Given the postfix expression

   A B + C D E + * *

   construct the corresponding expression tree.
4. If you perform an inorder traversal on an expression tree, what kind of expression do you get? What about postorder and preorder?

Advanced Topics

1. What is the primary motivation for using a Threaded Binary Tree? What problem does it solve?
2. Explain the difference between a right-threaded (one-way) and a two-way threaded binary tree.
3. Given the binary tree on page 96, draw its corresponding right-threaded binary tree, clearly indicating the threads with dotted lines.
4. What is the purpose of the boolean flag(s) (e.g., rightThread) in the node structure of a threaded binary tree?
5. Explain the Array Representation of a binary tree. If a node is at index i, what are the indices of its left and right children?
6. Describe the Left Child - Right Sibling representation for general trees.