# 18CS32 Data Structures and Applications Question Bank – 4

• ## Computer Graphics OpenGL Mini Projects

### MODULE – 4: TREES

1. Define tree? For a given tree explain the following

i) Root node ii) Degree iii) Sibling iv) Depth of a tree v) Ancestor

2. With an example, explain the different types of representation of tree.

3. Define a binary tree. With example show array and linked representation of binary tree.

4. Write an expression tree for an expression i) A / B + C * D + E ii) ((6+(3-2)*5)^2+3)

5. Mention different types of binary trees and explain briefly

6. State the properties of a binary tree in detail

7. Write the C-routines to traverse the given tree using

i) Inorder ii) Pre-order iii) Post-order

8. Construct the binary tree (B-tree) from the given traversals:

Preorder: i) ABDCEF ii) / + * 1 \$ 2 3 4 5 iii) A B D G C E H I F

In-order: BDAEFC 1 + 2 * 3 \$ 4 – 5 D G B A H E I C F

Postorder: DBFECA

9. Explain iterative inorder traversal and level order traversal with C routines.

10. List and discuss the additional operations of binary tree with appropriate examples.

11. What is threaded binary tree? Write the rules to construct the threads.

12. Write the node structures and C declaration of threaded binary tree.

13. Explain inorder traversal and insertion of a node in a threaded binary tree.

14. Describe the binary search tree with an example. Write the iterative and recursive function to search for a key value in a binary search tree.

15. Construct a binary search tree for the inputs

i) 22, 14, 18, 50, 9, 15, 7, 6, 12, 32, 25

ii) 14, 5, 6, 2, 18, 20, 16, -1, 21

16. Explain and write the analysis of searching and inserting a node in BST.