Binary Search Trees

Question 1

what is a binary search tree?

Answer 1

1 - binary tree (at most have 2 children)
2 - left subtrees are lesser than the parent
3 - right subtrees are greater than the parent

Question 2

where do u start in a BST?

Answer 2

we always start at the root of the tree

Question 3

what to do when u want to delete a node with two children?

Answer 3

you must search for the smallest bigger leaf than the node u want to remove and replace it with that node and then delete it

Question 4

what to do with duplicate values?

Answer 4

it depends on the application and if u insert it it would be better to insert it into the right of the node which makes it a stable tree

Question 5

what is the structure of a BST?

Answer 5

it has a linked list structure

Question 6

what does each node need?

Answer 6

1 - a value
2 - a parent
3 - a left child
4 - a right child

Question 7

what are the types of traversal in BST?

Answer 7

1 - PreOrder (DFS)
2 - PostOrder (DFS)
3 - InOrder
4 - Level Order (BDS)

Question 8

what is a PreOrder Traversal?

Answer 8

visit yourself
then visit all your left subtree
then visit all your right subtree

Question 9

what is a PostOrder Traversal?

Answer 9

then visit all your left subtree
then visit all your right subtree
visit yourself

Question 10

what is a InOrder Traversal?

Answer 10

then visit all your left subtree
visit yourself
then visit all your right subtree

Question 11

what is a Level Order Traversal?

Answer 11

it’s breadth first search where u can’t use recursion u must use a queue or a list
u add an element to the queue and go and remove it and when u remove it u add the children to the list as long as the queue is not empty

Question 12

why is BST better than binary search on an array?

Answer 12

cuz in an array insertion and removal is harder

Question 13

how to search in a BST?

Answer 13

1 - compare for the current element if they are equal return
2 - if it’s smaller go to the left
3 - if it’s bigger go to the right

Question 14

what is the airport reservation system problem?

Answer 14

u have an airport with landing zones and u want the airplanes to request for landing in T time to the set R and keep track of K (available time to land) and u want to delete from R set when a plane lands all of that in log(N)

Question 15

how to find min()

Answer 15

go to the left until there is no left

O(H) where h is the height

Question 16

how to find max()

Answer 16

go to the right until there is no right

O(H) where h is the height

Question 17

what is an augmented BST?

Answer 17

it’s a BST with a little more information in each node like the number of subtrees that each node has under it