Bissoy.com
Doctors Medicines MCQs Q&A

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

What are the worst-case complexities of insertion and deletion of a key in a binary search tree? Correct Answer θ (n) for both insertion and deletion

Concepts:

Minimum height of the tree is when all the levels of the binary search tree (BST) are completely filled.

Maximum height of the BST is the worst case when nodes are in skewed manner.

Formula:

Minimum height of the BST with n nodes is ⌈log2 (n + 1)⌉ - 1

The maximum height of the BST with n nodes is n - 1.

BST with a maximum height:

[ alt="zza05" src="//storage.googleapis.com/tb-img/production/17/03/zza05.JPG">

Insertion:

Traverser the BST to the maximum height

Worst-case time complexity of Insertion = θ (n - 1) ≡ θ (n)

Deletion:

Traverser the BST to the maximum height

Worst-case time complexity of  = θ (n - 1) ≡ θ (n)

Related Questions

We create a binary search tree B1 by inserting the numbers 1, 2, 3, 4, 5 into an empty binary search tree. We create another binary search tree B2 by inserting the numbers into an empty binary search tree in the reverse order. What is the difference between the right-most element of B1 and the left-most element of B2?
Which of the following is/are correct about a strictly binary tree? A. A binary tree is called strictly binary tree if every non-­leaf node of it has non empty left and right sub tree B. In strictly binary tree can have two children or no child C. A strictly binary tree with n leaves always contact 2n­-1 nodes
Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Which of the following is correct for the full binary tree?
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 representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode {              treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) {              int value=0;              if (tree != NULL) {              if (tree->leftMostChild == NULL)              value = 1;    else               value = DoSomething(tree->leftMostChild);               value = value + DoSomething(tree->rightSibling);     }               return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the 
Insertion into a 2-d tree is a trivial extension of insertion into a binary search tree.
For a tree with just one node, the root node, the height of a binary tree is defined to be zero; if there are 2 levels of nodes, the height is 1 and so on. Binary search tree is built according to the usual rules with the following six keys, inserted one at a time given: B, I, N, A, R, Y. what is the height of the tree?  
Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only
The following is the sequence of insertion in a binary search tree. 45,65,35,40,33,70,60,75,69 How many numbers of nodes in Left Sub Tree (LST) and Right Sub Tree (RST) of Root node.
What are the worst case and average case complexities of a binary search tree?
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?