t_id,6875-1 QUESTION 1 The complexity of deleting a value x in a BST of n elerme

Question

t_id,6875-1 QUESTION 1 The complexity of deleting a value x in a BST of n elerments and height his o 0(1) o o(n) o O(n log n) QUESTION 2 The complexity of postorder traversal of a binary tree is O O(n log n) O 0(log n) O(n) 0(1) QUESTION 3 The number of nodes of a binary tree of height is Between B(c and ehj where c is a constant d Between G(c log h) and eich) where cis a constant i1 Between @/h) and orch where c is a constantt Between e(h) and erhf) where c is a constant -1 QUESTION 4 The complexity of inserting a O(n) Oin log n)

Explanation / Answer

Answers :

1) O(h)

Comments :  there is therom in BST that is Insertion and deletion can be performed in O(h) time, where h is the height of the tree

2)  O(n)

Comments : The complexity of each of these Depth-first traversals is O(n+m). Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes. The complexity then becomes O(n + n-1), which is O(n)

3) Answer is 3rd

comments : The minimum number of nodes in a binary tree of height h = h + 1

The maximum number of nodes in a binary tree of height h = 2h+1 1

4) O(h)

Comments :  there is therom in BST that is Insertion and deletion can be performed in O(h) time, where h is the height of the tree

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.