Binary Search Tree Flashcards

1
Q

In what order are nodes accessed using Pre-order Traversal?

A

Root-Left-Right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

In what order are nodes accessed using In-order Traversal?

A

Left-Root-Right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

In what order are nodes accessed using Post-order Traversal?

A

Left-Right-Root

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the key steps for searching in a BST?

A
  1. Beginning from the root node, compare the target key to the current node key. If less-than follow the left child, if greater-than follow the right child.
  2. Repeat the process until target node is found where the current node key matches the target key.
  3. If the traversal ends without finding a match (reaching leaf node), the target key does not exist.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the key steps in adding a node to a BST?

A
  1. Beginning from the root node, compare the target key to the current node key. If less-than, traverse the left child, if greater-than, traverse the right child.
  2. Repeat the process until it reaches a leaf node. The new key will be added at the missing edge.
  3. If a matching key is found, the new key is not added to prevent duplicates.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the advantages of Binary Search Tree?

A
  • Enables the use of binary search on a data structure that is guaranteed to remain sorted.
  • Adding elements into a BST has a time complexity of O(log n), vs append-and-sort operations for an array which have a time complexity of O(n log n) using merge sort.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the disadvantages of Binary Search Tree?

A
  • Arrangements of nodes not stored, nodes of BST cannot be accessed by index
  • BST may become unbalanced in the course of usage and require balancing to maintain optimal performance
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

why do we need to recreate the binary search tree periodically

A
  • BST performs optimally when balanced
  • as entries are added and removed the tree may become unbalanced and recreating it will rebalance it again (making median element as root node)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly