Binary Search Tree (Module 8.2) PART II

Question 1

For the initial call for global range constraints, we should start with (______, ________) at the root of the tree.

Answer 1

(INT_MIN, INT_MAX)

Question 2

For the initial call, why do we start with (INT_MIN, INT_MAX)?

Answer 2

so the root can have any valid integer value

Question 3

For the left subtree in global constraints, when moving to the left child of a node with value v, the allowable range is updated to ______, ___).

Answer 3

(INT_MIN, v)

Question 4

For global contraints, why is (INT_MIN, v) used to update the range in the left subtree?

Answer 4

so all values in the left subtree are less than v

Question 5

For the left subtree in global constraints, when moving to the right child of a node with value v, the allowable range is updated to
(__, _______).

Answer 5

(v, INT_MAX)

Question 6

For global contraints, why is (v, INT_MAX) used to update the range in the right subtree?

Answer 6

so all values in the right subtree are larger than v

Question 7

Is Global binary search tree (BST) necessary for a binary tree to work as a valid binary search tree?

Answer 7

Yes!

Question 8

What are the 3 advantages of enforcing the Global BST property?

Answer 8

1) correctness
2) efficiency
3) avoid false positives

Question 9

For inserting in a BST, what happens to the new node if the tree is empty?

Answer 9

it becomes the root of the tree

Question 10

In a binary search tree (BST), insertions are always done at what level?

Answer 10

leaf node level

Question 11

Is it possible to insert a node at a non-leaf position without violating the global and local constraints of BST?

Answer 11

no! (it’s no longer a valid BST)

Question 12

What is the best case time complexity for a binary search tree insertion?

Answer 12

O(log n)

Question 13

What is the worst case time complexity for binary search tree insertion?

Answer 13

O(n)

Question 14

What is the space complexity for binary search tree insertion?

Answer 14

O(h)