Trees Programming 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.

Binary Search Tree

1. Implement a recursive function to create a BST and insert an item, ensuring duplicates are not allowed.
2. Implement both a recursive and an iterative function to search for a key in a BST, returning a pointer to the node or NULL if not found.
3. Write a function to find the maximum element in a BST (the rightmost node).
4. Write a function to find the minimum element in a BST (the leftmost node).
5. Implement an iterative function, Insert, to insert a new node into a BST after checking for duplicates and finding the correct position.
6. Implement a function, Delete, to delete a node from a BST, considering the three cases: deleting a leaf node, a node with one child, and a node with two children (e.g., replacing it with the inorder successor, the smallest element in the right subtree).

General Binary Tree Operations and Traversals

1. Implement a recursive function, CreateBinaryTree, to create a general binary tree based on user input for child nodes (e.g., using -1 as a sentinel value).
2. Implement a function, insert, to insert a new node at a position specified by a string of directions (e.g., "LLR") from the root.
3. Implement a recursive function, inorder, and an iterative function, iterative_inorder, for inorder traversal (LVR).
4. Implement a recursive function, preorder, and an iterative function for preorder traversal (VLR).
5. Implement a recursive function, postorder, and an iterative function for postorder traversal (LRV).
6. Implement a function, Levelorder, for level-order traversal using a queue.
7. Implement a recursive function, height, to find the height (or depth) of a binary tree.
8. Implement a recursive function, copy, to create an exact copy of a given binary tree.
9. Implement a function, Equal, to test if two binary trees are equal (same topology and identical node data).
10. Implement a function, count_nodes, to count the total number of nodes in a tree by traversing it.
11. Implement a function, count_leafnodes, to count the number of leaf nodes in a binary tree.

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.