Recent questions tagged binary-search-tree

How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$

A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys.$81, 537, 102, 439, 285, 376, 305$$52, 97, 121, 195, 242, 381...

A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys.$81, 537, 102, 439, 285, 376, 305$$52, 97, 121, 195, 242, 381...

Which of the following is TRUE?The cost of searching an AVL tree is $\Theta (\log n)$ but that of a binary search tree is $O(n)$The cost of searching an AVL tree is $\The...

A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain.$\begin{array}{llllll} \text{(a)} ...

A binary search tree is generated by inserting in order the following integers:$$50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$$The number of nodes in the left subtree and ...

A binary search tree contains the value $1, 2, 3, 4, 5, 6, 7, 8$. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a...

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$...

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 sam...

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?$O(1)$$O(\log n)$...

How many distinct binary search trees can be created out of $4$ distinct keys?$5$$14$$24$$42$

Postorder traversal of a given binary search tree, $T$ produces the following sequence of keys$10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29$Which one of the following se...

What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$.$2$$3$$4$$5$

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ ...

The following numbers are inserted into an empty binary search tree in the given order: $10, 1, 3, 5, 15, 12, 16$. What is the height of the binary search tree (the heigh...

A data structure is required for storing a set of integers such that each of the following operations can be done in $O(\log n)$ time, where $n$ is the number of elements...

Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering o...

Let $T(n)$ be the number of different binary search trees on $n$ distinct elements.Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is $n-k+1$$n-k$$n-k-1$$n-k-2$

Insert the following keys one by one into a binary search tree in the order specified.$$15, 32, 20, 9, 3, 25, 12, 1$$Show the final binary search tree after the insertion...

You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P...

The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is$\Theta(n\log n)$$\Theta(n2^n)$$\Theta(n)$$\Theta(\log n)$