Multiple Choice Questions

1. Threaded Binary Tree: If a binary tree is threaded for in-order traversal a right NULL link of any node is replaced by the address of its [WBUT 2007, 2016]
   a) successor ✓ b) predecessor c) root d) own

2. AVL Tree: In a height balanced tree the heights of two sub-trees of every node never differ by more than [WBUT 2007, 2009, 2018]
   a) 2 b) 0 c) 1 ✓ d) -1

3. AVL Tree: Maximum possible height of an AVL Tree with 7 nodes is [WBUT 2007, 2009, 2018]
   a) 3 ✓ b) 4 c) 5 d) 6

4. B-Tree: A B-tree is [WBUT 2008, 2018]
   a) Always balanced b) An ordered tree c) A direct tree d) All of these ✓

5. Array Representation: In array representation of Binary tree, if the index number of a child node is 6 then the index number of its parent node is [WBUT 2010, 2014]
   a) 2 b) 3 ✓ c) 4 d) 5

6. Complete Binary Tree: The depth of a complete binary tree with n nodes [WBUT 2012]
   a) log(n+1)-1 ✓ b) log(n) c) log(n-1)+1 d) log(n)+1

7. Binary Search Tree: In a binary search tree, if the number of nodes of a tree is 9, then the minimum height of the tree is [WBUT 2012]
   a) 9 b) 5 c) 4 d) None of these ✓

8. Traversal Methods: Which method of traversal does not use stack to hold nodes that are waiting to be processed: [WBUT 2012]
   a) Breadth-first ✓ b) Depth-first c) D-search d) None of these

9. Expression Conversion: Which of the following is essential for converting an infix expression to the postfix expression efficiently? [WBUT 2013]
   a) An operator stack ✓ b) An operand stack c) An operand stack and operator stack d) A parse tree

10. Binary Trees: Number of all possible binary trees with 4 nodes is [WBUT 2013]
    a) 13 b) 12 c) 14 ✓ d) 15

11. Tree Traversal: If the inorder and preorder traversal of a binary tree are D, B, F, E, G, H, A, C and A, B, D, E, F, G, H, C respectively then, the postorder traversal of that tree is [WBUT 2013]
    a) D, F, G, A, B, C, H, E b) F, H, D, G, E, B, C, A c) C, G, H, F, E, D, B, A d) D, F, H, G, E, B, C, A ✓

12. Binary Trees: The number of possible distinct binary trees with 12 nodes is [WBUT 2013]
    a) 4082 b) 4084 ✓ c) 3084 d) 3082

13. Binary Tree Properties: A binary tree has n leaf nodes. The number of nodes of degree 2 in this tree is [WBUT 2015]
    a) log n b) n-1 c) n d) cannot be said ✓

14. Binary Tree Height: The minimum height of a binary tree of n nodes is [WBUT 2015]
    a) n b) n/2 c) n/2-2 d) ⌈log₂(n+1)⌉-1 ✓

15. Full Binary Tree: The number of edges in a full binary tree of height h is [WBUT 2015]
    a) 2^(h+1)-1 b) 2^h-1 c) 2^(h+1)-2 ✓ d) 2^h-2

16. Complete Binary Tree: Minimum number of nodes required to make a complete binary tree of height h is [WBUT 2017]
    a) 2^h-1 b) 2^h ✓ c) 2^h+1 d) 2^(h-1)

17. Tree Reconstruction: Which one is required to reconstruct a binary tree? [WBUT 2017]
    a) Only inorder sequence b) Both preorder and postorder sequences c) Both inorder and postorder sequences ✓ d) Only postorder sequence

18. Complete Binary Tree: Number of nodes in a complete binary tree of depth k is [WBUT 2018]
    a) 2^k b) 2k c) 2^k-1 ✓ d) None of these

19. Full Binary Tree: A full binary tree with n non-leaf nodes contains [WBUT 2019]
    a) log 2n nodes b) n+1 nodes c) 2n nodes ✓ d) 2n+1 nodes

20. BST Traversal: The values in a BST can be sorted in ascending order by using which of the traversals method? [WBUT 2022]
    Answer: In-order traversal

Short Answer Type Questions

1. Expression Tree: Construct the expression tree for the following expression: E = (2a + 5b)(x - 7y)^4 [WBUT 2010]

2. Threaded Binary Tree: Write an algorithm for non-recursive in-order traversal of a threaded binary tree. [WBUT 2011, 2018]

3. In-order Successor: Write a C language function to find the In-order successor of the root of a binary tree. [WBUT 2011]

4. BST Validation: Write an algorithm to test whether a given binary tree is a binary search tree. [WBUT 2011]

5. Tree Rotation: Write an algorithm to left rotate a binary tree. [WBUT 2011]

6. Binary Tree Construction: What is binary tree? Construct a binary tree using the Inorder and Postorder traversal of the node given below: Inorder: DBFEAGCLJHK Postorder: DFEBGLJKHCA [WBUT 2012]

7. AVL Tree Construction: Construct an AVL tree using the below list. Show all the steps: 12, 11, 13, 10, 09, 15, 14, 18, 7, 6, 5, 4 [WBUT 2012]

8. Binary Tree Property: Prove that the maximum no. of nodes in a binary tree of depth k is 2^k - 1. [WBUT 2014]

9. Expression Tree: For the following expression draw the corresponding expression tree: a + b*c - d/e [WBUT 2014]

10. B-Tree Properties:
    a) Does a B tree grow at its leaves or at its root? Why? [WBUT 2016]
    b) In deleting a key from a B tree, when is it necessary to combine nodes?

11. Tree Construction: The post-order and in-order traversal sequences of codes in a binary tree are given below: Post-order: D G E B H I F C A Pre-order: D B G E A C H F I Construct the binary tree. [WBUT 2016]

12. B-Tree Construction: Construct one B-Tree of order 4 with the following data: 34, 67, 89, 90, 100, 2, 36, 76, 53, 51, 12, 10, 77, 69. [WBUT 2016]

13. Expression Tree from Postfix: Construct a tree from the given postfix expression: abc* + de* f + g* + [WBUT 2016]

14. Tree Reconstruction from Traversals: The Inorder and preorder tree traversals are given. Draw the binary tree: Inorder: ABCDEFGHI Preorder: FBADCEGHI. Is it possible to build up a unique binary tree when its preorder and postorder traversals are given? [WBUT 2017]

15. B-Tree Insertion: Insert the following keys into a B-Tree of given order mentioned below:
    a) a, f, b, k, h, m, e, s, r, c (Order 3) [WBUT 2018]
    b) a, g, f, b, k, d, h, m, j, e, s, l, r, x, c, l, n, t, u, p (Order 5) [WBUT 2018]

16. Expression Tree: What is expression tree? Draw the expression tree and write the In, Pre & Post-Order traversals for the given expression: E = (2x + y)(5a - b)^3 [WBUT 2018]

17. B-Tree vs B+ Tree: Write difference between B tree and B+ tree. [WBUT 2022]

Long Answer Type Questions

1. BST Insertion: Write an algorithm to insert a node in a binary search tree. [WBUT 2007, 2014]

2. Non-recursive Traversal: Write a non-recursive algorithm for in-order traversal of a binary tree. [WBUT 2007, 2010, 2016]

3. Threaded Binary Tree:
   a) What is threaded binary tree? [WBUT 2008, 2011]
   b) Write an algorithm to delete a node from a binary search tree. [WBUT 2008, 2019]

4. AVL Tree Construction:
   a) Show the steps in creation of a height balanced binary AVL TREE using insertion of items: March, May, November, August, April, January, December, July, February, June, October, September [WBUT 2009]
   b) What do you mean by a B-Tree and what are the uses of such a tree? [WBUT 2009, 2016]
   c) Consider a B-Tree of order 5 and insert elements 4, 5, 58, 6 [WBUT 2009]

5. B-Tree Construction: Show the stages in growth of an order-4 B-tree when the following keys are inserted: 74 72 19 87 51 10 35 18 39 60 76 58 19 45 [WBUT 2010]

6. AVL vs BST: How an AVL tree differs from binary search tree? [WBUT 2010, 2012]

7. Tree from Traversals: Given the preorder and inorder sequence, draw the resultant binary tree and write its postorder traversal: Pre-order: A B D G H E I C F J K, In-order: G D H B E I A C J F K. Write an algorithm to search a node in a binary search tree. [WBUT 2010]

8. Height-Balanced Trees: What are the problems of binary tree? Explain the improvement of performance by the use of height-balanced tree. Show how a height-balanced tree can be formed by inserting: 1,2,3,4,5,6,8,9,10,7,11. Show the root element that can be deleted from the above tree. [WBUT 2010]

9. B-Tree Alphabet Insertion: What is a B-tree? Show how the letters A to P of English alphabet can be entered into a B-tree of order 4. [WBUT 2011]

10. BST Operations: Insert the following numbers into a binary search tree: 87, 36, 22, 15, 56, 85, 48, 91, 72, 6. Delete 48 and draw the resulting tree. Delete 15 and draw the resulting tree. [WBUT 2014]

11. Advanced Tree Operations:
    a) Show the stages in growth of an order-4 B-Tree when keys are inserted: 84 82 29 97 61 10 45 28 49 70 86 68 19 55 22 11 55 7 16 [WBUT 2014]
    b) How does an AVL tree differ from a binary search tree? Insert keys: 8 12 9 11 7 6 66 2 1 44 into an AVL tree. Mention rotations used and balance factor of each node. [WBUT 2014, 2019]

12. Tree from Postorder & Inorder: The post-order and in-order traversal sequences are: Post-order: IEJFCGKLHDBA, In-order: EICFJBGDKHLA. Construct the tree. Write an algorithm for inserting an element into a Binary tree with example. [WBUT 2015]

13. BST Min/Max: Write a C function to find out the maximum and the minimum elements in a binary search tree. Given the pre-order sequence and the post-order sequence, why cannot you reconstruct the tree? [WBUT 2016]

14. Binary Search Tree:
    a) What do you mean by a binary search tree?
    b) Construct a binary search tree by inserting: 13, 10, 3, 5, 18, 15, 14
    c) Write an algorithm for pre-order traversal of a tree represented by a linked-list. [WBUT 2016]

15. AVL Tree with Strings:
    a) What is an AVL tree? [WBUT 2017]
    b) Construct an AVL search tree for the data list: AND, BEGIN, CASE, DO, END, FOR, GOTO
    c) For the AVL tree constructed, delete the following keys in order: DO, FOR, END

16. AVL Rotations:
    a) Explain different rotation mechanisms in AVL tree. [WBUT 2019]
    b) Show that for a non-empty binary tree, if n₀ is the number of leaf nodes and n₂ is the number of nodes of degree 2 then n₀ = n₂ + 1.

17. BST Construction & Deletion:
    a) Create a binary search tree using: 54, 60, 69, 32, 46, 25, 81, 29, 75, 78 [WBUT 2019]
    b) Explain with example the process of deleting a node from a binary search tree.

18. Short Notes: Write short notes on the following:
    a) AVL Tree
    b) Threaded Binary Tree
    c) B-tree
    d) Binary Search Tree [WBUT 2019]

---

Top 20 Predicted Questions for WBUT 2026 Examination

Most Important Questions (Based on Frequency & Trends)

Question 1: Binary Tree Properties

Prove that for any non-empty binary tree, number of leaf nodes (n₀) = number of nodes with degree 2 (n₂) + 1. [Repeated concept - WBUT 2019]

Question 2: AVL Tree Construction & Rotations

Construct an AVL tree by inserting the following elements in the given order. Show all steps including rotations and balance factors:
50, 40, 30, 60, 55, 70, 45, 35, 25 [Similar to WBUT 2009, 2012, 2014, 2019]

Question 3: Tree Reconstruction from Traversals

Given the following traversals of a binary tree, construct the unique binary tree:
Inorder: D B E A F C G
Preorder: A B D E C F G
Also write the postorder traversal of the constructed tree. [Similar to WBUT 2010, 2012, 2013, 2015, 2016, 2017]

Question 4: B-Tree Construction

Construct a B-Tree of order 5 by inserting the following keys sequentially. Show all steps including splits:
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70 [Similar to WBUT 2009, 2010, 2011, 2014, 2016, 2018]

Question 5: BST Deletion (All Cases)

Write an algorithm to delete a node from a Binary Search Tree considering all three cases (no child, one child, two children). Demonstrate with an example by deleting nodes 30, 45, and 50 from a BST. [WBUT 2008, 2014, 2019]

Question 6: Expression Tree

Construct an expression tree for the following expression and write its inorder, preorder, and postorder traversals:
E = (a + b * c) / (d - e) ^ f [Similar to WBUT 2010, 2014, 2016, 2018]

Question 7: Threaded Binary Tree

What is a Threaded Binary Tree? Explain with a diagram how threading works for inorder traversal. Write an algorithm for non-recursive inorder traversal of a threaded binary tree. [WBUT 2008, 2011, 2018]

Question 8: BST Validation

Write an algorithm to test whether a given binary tree is a Binary Search Tree. Analyze its time complexity. [WBUT 2011]

Question 9: Maximum Nodes in Binary Tree

Prove that the maximum number of nodes in a binary tree of height h is 2^h - 1. [WBUT 2014]

Question 10: B-Tree vs B+ Tree

Differentiate between B-Tree and B+ Tree with respect to structure, pointers, search efficiency, and applications. [WBUT 2022]

Question 11: AVL Tree Balance Factor

Explain the concept of balance factor in AVL trees. Show the steps to insert 10, 20, 30, 40, 50, 25 into an initially empty AVL tree. Mention the rotations used at each step. [WBUT 2014]

Question 12: Non-recursive Tree Traversal

Write a non-recursive algorithm for inorder traversal of a binary tree using a stack. Explain with an example. [WBUT 2007, 2010, 2016]

Question 13: Binary Tree Properties

A binary tree has 20 nodes. Find the minimum possible height and maximum possible height of this tree. Justify your answer. [Related to WBUT 2012, 2015]

Question 14: BST Search & Insert

Write C functions to:
a) Search for an element in a Binary Search Tree
b) Insert an element into a Binary Search Tree [WBUT 2007, 2010, 2014, 2015]

Question 15: Complete Binary Tree

Define a complete binary tree. Find the number of nodes in a complete binary tree of depth 5. Also find the depth of a complete binary tree with 100 nodes. [WBUT 2012, 2017, 2018]

Question 16: AVL Rotations (All Types)

Explain all four types of rotations used in AVL trees (LL, RR, LR, RL) with suitable diagrams and examples. [WBUT 2019]

Question 17: Tree Traversal Methods

Compare and contrast the different tree traversal methods (inorder, preorder, postorder, level-order). Give applications of each traversal type. [WBUT 2012, 2022]

Question 18: B-Tree Deletion

Explain the process of deleting a key from a B-Tree. When is node combination (merging) required? Give an example. [WBUT 2016]

Question 19: Binary Tree Array Representation

A binary tree is stored in an array such that for a node at index i, its left child is at 2i+1 and right child at 2i+2. If a node is at index 7, find its parent, left child (if exists), and right child (if exists). [WBUT 2010, 2014]

Question 20: BST Minimum Height

Show that the minimum height of a Binary Search Tree with n nodes is ⌈log₂(n+1)⌉-1. What is the maximum height? Explain with examples. [WBUT 2012, 2015]

---

Additional Important Topics (May appear)

1. Height-Balanced Tree Advantages: Explain the problems with ordinary BST and how AVL trees overcome them. [WBUT 2010]

2. Binary Tree from Postfix: Construct a tree from postfix expression and evaluate it. [WBUT 2016]

3. Tree Terminology: Define all basic terminology related to trees (root, leaf, internal node, degree, path, etc.) with examples.

4. Binary Search Tree Properties: Prove that inorder traversal of a BST gives sorted order.