1. Home
  2. GATE CS
  3. Programming and Data Stru...

Filters

Found 2 Questions

Set Default
Exams
Years
Subjects
Topics

List of top Programming and Data Structures Questions on Binary Search Trees - Insertion Order and Tree Shape asked in GATE CS

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 \(Val(V)\). All the keys present in the given BST are distinct. The keys belong to the set of real numbers.

For a node \(V\), let \(Suc(V)\) denote the node that is its inorder successor. If a node \(V\) does not have an inorder successor, then \(Suc(V)\) is \(NULL\). As there are no duplicates, if \(Suc(V)\) is not \(NULL\), then \(Val(V) < Val(Suc(V))\).

Corresponding to every leaf node \(L_i\) that has a non-NULL \(Suc(L_i)\), a new key \(k_i\) with the following property is to be inserted into the BST. \[ Val(L_i) < k_i < Val(Suc(L_i)) \] Let \(K\) represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?
  • GATE CS - 2026
  • GATE CS
  • Programming and Data Structures
  • Binary Search Trees - Insertion Order and Tree Shape
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 one of the following elements can NEVER be the third element that is inserted?
  • GATE CS - 2026
  • GATE CS
  • Programming and Data Structures
  • Binary Search Trees - Insertion Order and Tree Shape
contact us
terms & conditions
Privacy & Policy
© 2026 Patronum Web Private Limited