Binary Trees, Binary Search Trees and Balanced Trees: GATE CS previous year questions (Data Structures)

GATE CS 2026 Set 1NAT1 markEasy (estimate)
GATE CS 2026 Set 1, Q.33
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 binary tree with 23 nodes is __...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 1MCQ2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.40
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 binary tree. Which...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 1NAT2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.62
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 element $60$ in the...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 2MCQ1 markEasy (estimate)
GATE CS 2026 Set 2, Q.12
The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal. T S I: Inorder L: left subtree, node, right subtre...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 2MSQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.49
Consider a binary search tree (BST) with $n$ leaf nodes ( $n > 0$ ). Given any node $V$ , the key present in the node is denoted as $V a l (V)$ . All the keys present in the given BST...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 1MSQ1 markEasy (estimate)
GATE CS 2025 Set 1, Q.26
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 2MCQ1 markEasy (estimate)
GATE CS 2025 Set 2, Q.13
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 number of nodes in…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 2NAT1 markEasy (estimate)
GATE CS 2025 Set 2, Q.35
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 search tree. The number...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 2MCQ2 marksMedium (estimate)
GATE CS 2025 Set 2, Q.38
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 structures: P: Unsorted doub...
Arrays and Linked Lists · Binary Heaps and Priority Queues · Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2024 Set 2MCQ2 marksEasy (estimate)
GATE CS 2024 Set 2, Q.39
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. The tree $T$ follows...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2023MCQ2 marksEasy (estimate)
GATE CS 2023, Q.47
Consider the C function foo and the binary tree shown. Binary tree with root 10, left child 5 (with left child 3 and right child 8), and right child 11 (with right child 13). ty...
Binary Trees, Binary Search Trees and Balanced Trees · Functions, Recursion, Scope and Storage Classes
GATE CS 2022NAT1 markHard (estimate)
GATE CS 2022, Q.28
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that th...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2021 Set 1MCQ1 markMedium (estimate)
GATE CS 2021 Set 1, Q.20 (CS Q.10)
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 in $T$ ?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2021 Set 2NAT1 markEasy (estimate)
GATE CS 2021 Set 2, Q.26 (CS Q.16)
Consider a complete binary tree with 7 nodes. Let $A$ denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let $B$ denote...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2020MCQ1 markEasy (estimate)
GATE CS 2020, Q.15 (CS Q.5)
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?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2020MCQ1 markMedium (estimate)
GATE CS 2020, Q.16 (CS Q.6)
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
GATE CS 2020MCQ2 marksEasy (estimate)
GATE CS 2020, Q.51 (CS Q.41)
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 number of reported elemen...
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
GATE CS 2019NAT2 marksMedium (estimate)
GATE CS 2019, Q.56 (CS Q.46)
Let $T$ be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. T...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2018NAT1 markEasy (estimate)
GATE CS 2018, Q.30 (CS Q.20)
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 the length of the longest pat...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2017 Set 1MCQ1 markEasy (estimate)
GATE CS 2017 Set 1, Q.6 (CS Q.6)
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.
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2017 Set 2MCQ2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.36 (CS Q.36)
The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.46 (CS Q.36)
Consider the following New-order strategy for traversing a binary tree: - Visit the root; - Visit the right subtree using New-order; - Visit the left subtree using New-order; Th...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2016 Set 2NAT2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.50 (CS Q.40)
The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is ________. Note: The hei...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.20 (CS Q.10)
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$ III.…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.33 (CS Q.23)
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.35 (CS Q.25)
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:
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 2NAT1 markEasy (estimate)
GATE CS 2015 Set 2, Q.20 (CS Q.10)
A binary tree $T$ has 20 leaves. The number of nodes in $T$ having two children is _____.
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 3MCQ1 markEasy (estimate)
GATE CS 2015 Set 3, Q.23 (CS Q.13)
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 3NAT1 markEasy (estimate)
GATE CS 2015 Set 3, Q.35 (CS Q.25)
Consider a binary tree $T$ that has 200 leaf nodes. Then, the number of nodes in $T$ that have exactly two children are _____.
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 1NAT1 markMedium (estimate)
GATE CS 2014 Set 1, Q.22 (CS Q.12)
Consider a rooted $n$ node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 2NAT2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.49 (CS Q.39)
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possib...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 3MCQ1 markMedium (estimate)
GATE CS 2014 Set 3, Q.22 (CS Q.12)
Consider the following rooted tree with the vertex labeled P as the root: Rooted tree with root P having left child Q and right child R; Q has child S; R has three children T, U...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 3NAT2 marksMedium (estimate)
GATE CS 2014 Set 3, Q.49 (CS Q.39)
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 3MCQ2 marksMedium (estimate)
GATE CS 2014 Set 3, Q.51 (CS Q.41)
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling repres...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2013MCQ1 markEasy (estimate)
GATE CS 2013, Q.7 (CS Q.7)
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2013MCQ2 marksEasy (estimate)
GATE CS 2013, Q.43 (CS Q.43)
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.5 (CS Q.5)
The worst case running time to search for an element in a balanced binary search tree with $n 2^{n}$ elements is
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2012MCQ2 marksEasy (estimate)
GATE CS 2012, Q.47 (CS Q.47)
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the he...
Binary Trees, Binary Search Trees and Balanced Trees · Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2011MCQ1 markEasy (estimate)
GATE CS 2011, Q.23 (CS Q.23)
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2011MCQ2 marksEasy (estimate)
GATE CS 2011, Q.29 (CS Q.29)
We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary...
Binary Trees, Binary Search Trees and Balanced Trees

Questions

Other topics of Data Structures