The GATE Grind

GATE Programming and Data Structures: Trees and Binary Search Trees – Previous Year Questions

46 GATE previous year questions on Trees and Binary Search Trees (Programming and Data Structures, Computer Science) with answers and explanations, from every paper.

46 questions worth 68 marks in all (24 1-mark, 22 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q12 (1 mark, Multiple choice) – Tree height is the maximum number of root-to-leaf edges. What maximum nodes can a height-h binary tree have?
  2. GATE 2007 CS Q13 (1 mark, Multiple choice) – How many different binary trees can be formed with three unlabeled nodes?
  3. GATE 2007 CS Q39 (2 marks, Multiple choice) – A binary tree has inorder d b e a f c g and preorder a b d e c f g. What is its postorder?
  4. GATE 2007 CS Q43 (2 marks, Multiple choice) – A complete n-ary tree has either n children or none at each node. It has I internal nodes and L leaves. If L=41, I=10, find n.
  5. GATE 2007 CS Q46 (2 marks, Multiple choice) – CellNode is a binary-tree node. What does GetValue(root) return?
  6. GATE 2008 CS Q41 (2 marks, Multiple choice) – An order4 B-tree is built from scratch using10 successive insertions. What maximum number of node splits can occur?
  7. GATE 2008 CS Q46 (2 marks, Multiple choice) – Given postorder P of a BST containing1, 2, …, n, what is the most efficient complexity for determining the unique BST with that traversal?
  8. GATE 2009 CS Q37 (2 marks, Multiple choice) – What is the maximum height of an AVL tree with7 nodes? A one-node tree has height0.
  9. GATE 2021 CS (CS2) Q26 (1 mark, Numerical answer) – In a complete binary tree with seven nodes, A is the set of the first three nodes visited by root-started BFS and B the set of the first three visited…
  10. GATE 2015 CS (CS3) Q21 (1 mark, Numerical answer) – A binary tree has 200 leaves. How many nodes have exactly two children?
  11. GATE 2015 CS (CS3) Q27 (1 mark, Multiple choice) – Insert 71,65,84,69,67,83 into an empty binary search tree in this order. Which element is at the deepest level?
  12. GATE 2015 CS (CS2) Q23 (1 mark, Numerical answer) – A binary tree T has 20 leaves. How many nodes have exactly two children?
  13. GATE 2010 CS Q20 (1 mark, Multiple choice) – In a binary tree with n nodes, every node has an odd number of descendants, counting itself. How many nodes have exactly one child?
  14. GATE 2011 CS Q39 (2 marks, Multiple choice) – An unlabelled binary-tree shape has n nodes and n distinct keys are supplied. In how many ways can the keys populate it to make a BST?
  15. GATE 2013 CS Q17 (1 mark, Multiple choice) – What is the tightest worst-case upper bound for inserting into a binary search tree with n nodes?
  16. GATE 2013 CS Q53 (2 marks, Multiple choice) – A BST has preorder 30,20,10,15,25,23,39,35,42. Find its postorder.
  17. GATE 2012 CS Q57 (2 marks, Multiple choice) – Height counts edges on the longest downward path. Fill B1 and B2.
  18. GATE 2017 CS (CS2) Q46 (2 marks, Multiple choice) – BST preorder is 12,8,6,2,7,9,10,16,15,19,17,20. Find its postorder.
  19. GATE 2016 CS (CS2) Q21 (1 mark, Numerical answer) – BFS starts at the root of a binary tree. A vertex t is at distance four. If t is the n-th vertex visited, find the maximum n.
  20. GATE 2016 CS (CS2) Q46 (2 marks, Multiple choice) – New-order traversal visits root, then right subtree in New-order, then left subtree in New-order. Find it for the tree of postfix expression “3 4 * 5…
  21. GATE 2016 CS (CS2) Q50 (2 marks, Numerical answer) – How many insertion orders of 1,2,3,4,5,6,7 give a binary search tree of height six? A single-node tree has height zero.
  22. GATE 2014 CS (CS3) Q22 (1 mark, Multiple choice) – In the rooted tree shown, P is the root. In what order are the nodes visited during an in-order traversal?
  23. GATE 2014 CS (CS3) Q49 (2 marks, Numerical answer) – A balanced BST T holds n numbers. To sum the m numbers between given L and H, the tightest upper bound is O(nabn+mcdn). Find a+10b+100c+1000d.
  24. GATE 2014 CS (CS3) Q51 (2 marks, Multiple choice) – An arbitrary tree uses leftMostChild–rightSibling representation. When its root is passed to DoSomething, what does the returned value count? typedef…
  25. GATE 2014 CS (CS2) Q49 (2 marks, Numerical answer) – Each leaf of the shown expression tree independently has value 0 or 1. Find the maximum value of the expression over all leaf assignments.
  26. GATE 2014 CS (CS1) Q22 (1 mark, Numerical answer) – A rooted n-node binary tree is represented using pointers. The best upper bound for counting subtrees with exactly four nodes is O(nabn). Find a +…
  27. GATE 2017 CS (CS1) Q16 (1 mark, Multiple choice) – Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: Note: The height of a tree with a single node is 0.
  28. GATE 2015 CS (CS1) Q15 (1 mark, Multiple choice) – The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
  29. GATE 2015 CS (CS1) Q17 (1 mark, Multiple choice) – Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25…
  30. GATE 2015 CS (CS1) Q35 (1 mark, Multiple choice) – What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
  31. GATE 2018 CS Q30 (1 mark, Numerical answer) – The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is…
  32. GATE 2026 CS (CS2) Q12 (1 mark, Multiple choice) – The set T represents various traversals over a binary tree. The set S represents the order of visiting nodes during a traversal. I: Inorder II:…
  33. GATE 2026 CS (CS2) Q49 (2 marks, Multiple select) – Consider a binary search tree (BST) with n leaf nodes, where n>0. All keys are distinct real numbers. For a node V, let Suc(V) denote its inorder…
  34. GATE 2026 CS (CS1) Q33 (1 mark, Numerical answer) – The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full…
  35. GATE 2026 CS (CS1) Q40 (2 marks, Multiple choice) – Let P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a binary search tree that creates a complete…
  36. GATE 2026 CS (CS1) Q62 (2 marks, Numerical answer) – The following sequence corresponds to the preorder traversal of a binary search tree T: 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77 The position of the…
  37. GATE 2025 CS (CS2) Q13 (1 mark, Multiple choice) – Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the…
  38. GATE 2025 CS (CS2) Q35 (1 mark, Numerical answer) – Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let T be the resulting binary…
  39. GATE 2025 CS (CS2) Q38 (2 marks, Multiple choice) – A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data…
  40. GATE 2025 CS (CS1) Q26 (1 mark, Multiple select) – Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?
  41. GATE 2024 CS (CS2) Q39 (2 marks, Multiple choice) – You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by one, starting with an empty tree.…
  42. GATE 2023 CS Q47 (2 marks, Multiple choice) – Consider the C function foo and the binary tree shown. When foo is called with a pointer to the root node of the given binary tree, what will it…
  43. GATE 2021 CS (CS1) Q20 (1 mark, Multiple choice) – A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element…
  44. GATE 2020 CS Q15 (1 mark, Multiple choice) – The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
  45. GATE 2020 CS Q16 (1 mark, Multiple choice) – What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
  46. GATE 2020 CS Q51 (2 marks, Multiple choice) – In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the…