Binary Search Tree Flashcards
1
Q
In what order are nodes accessed using Pre-order Traversal?
A
Root-Left-Right
2
Q
In what order are nodes accessed using In-order Traversal?
A
Left-Root-Right
3
Q
In what order are nodes accessed using Post-order Traversal?
A
Left-Right-Root
4
Q
What are the key steps for searching in a BST?
A
- 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.
- Repeat the process until target node is found where the current node key matches the target key.
- If the traversal ends without finding a match (reaching leaf node), the target key does not exist.
5
Q
What are the key steps in adding a node to a BST?
A
- 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.
- Repeat the process until it reaches a leaf node. The new key will be added at the missing edge.
- If a matching key is found, the new key is not added to prevent duplicates.
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.
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
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)