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.
- GATE 2007 CS Q12 – Tree height is the maximum number of root-to-leaf edges. What maximum nodes can a height-h binary tree have?
- GATE 2007 CS Q13 – How many different binary trees can be formed with three unlabeled nodes?
- GATE 2007 CS Q39 – 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?
- GATE 2007 CS Q43 – 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.
- GATE 2007 CS Q46 – CellNode is a binary-tree node. What does GetValue(root) return?
- GATE 2008 CS Q41 – An order4 B-tree is built from scratch using10 successive insertions. What maximum number of node splits can occur?
- GATE 2008 CS Q46 – Given postorder P of a BST containing1, 2, …, n, what is the most efficient complexity for determining the unique BST with that traversal?
- GATE 2009 CS Q37 – What is the maximum height of an AVL tree with7 nodes? A one-node tree has height0.
- GATE 2021 CS (CS2) Q26 – 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…
- GATE 2015 CS (CS3) Q21 – A binary tree has 200 leaves. How many nodes have exactly two children?
- GATE 2015 CS (CS3) Q27 – Insert 71,65,84,69,67,83 into an empty binary search tree in this order. Which element is at the deepest level?
- GATE 2015 CS (CS2) Q23 – A binary tree T has 20 leaves. How many nodes have exactly two children?
- GATE 2010 CS Q20 – In a binary tree with n nodes, every node has an odd number of descendants, counting itself. How many nodes have exactly one child?
- GATE 2011 CS Q39 – 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?
- GATE 2013 CS Q17 – What is the tightest worst-case upper bound for inserting into a binary search tree with n nodes?
- GATE 2013 CS Q53 – A BST has preorder 30,20,10,15,25,23,39,35,42. Find its postorder.
- GATE 2012 CS Q57 – Height counts edges on the longest downward path. Fill B1 and B2.
- GATE 2017 CS (CS2) Q46 – BST preorder is 12,8,6,2,7,9,10,16,15,19,17,20. Find its postorder.
- GATE 2016 CS (CS2) Q21 – 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.
- GATE 2016 CS (CS2) Q46 – 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…
- GATE 2016 CS (CS2) Q50 – 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.
- GATE 2014 CS (CS3) Q22 – In the rooted tree shown, P is the root. In what order are the nodes visited during an in-order traversal?
- GATE 2014 CS (CS3) Q49 – 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.
- GATE 2014 CS (CS3) Q51 – An arbitrary tree uses leftMostChild–rightSibling representation. When its root is passed to DoSomething, what does the returned value count? typedef…
- GATE 2014 CS (CS2) Q49 – Each leaf of the shown expression tree independently has value 0 or 1. Find the maximum value of the expression over all leaf assignments.
- GATE 2014 CS (CS1) Q22 – 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 +…
- GATE 2017 CS (CS1) Q16 – 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.
- GATE 2015 CS (CS1) Q15 – 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
- GATE 2015 CS (CS1) Q17 – 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…
- GATE 2015 CS (CS1) Q35 – What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
- GATE 2018 CS Q30 – 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…
- GATE 2026 CS (CS2) Q12 – 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:…
- GATE 2026 CS (CS2) Q49 – 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…
- GATE 2026 CS (CS1) Q33 – 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…
- GATE 2026 CS (CS1) Q40 – 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…
- GATE 2026 CS (CS1) Q62 – 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…
- GATE 2025 CS (CS2) Q13 – 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…
- GATE 2025 CS (CS2) Q35 – 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…
- GATE 2025 CS (CS2) Q38 – 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…
- GATE 2025 CS (CS1) Q26 – Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?
- GATE 2024 CS (CS2) Q39 – 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.…
- GATE 2023 CS Q47 – 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…
- GATE 2021 CS (CS1) Q20 – 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…
- GATE 2020 CS Q15 – 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?
- GATE 2020 CS Q16 – What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
- GATE 2020 CS Q51 – 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…