Binary Search Tree

Question 1

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

Answer 1

Root-Left-Right

Question 2

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

Answer 2

Left-Root-Right

Question 3

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

Answer 3

Left-Right-Root

Question 4

What are the key steps for searching in a BST?

Answer 4

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.

Question 5

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

Answer 5

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.

Question 6

What are the advantages of Binary Search Tree?

Answer 6

• 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.

Question 7

What are the disadvantages of Binary Search Tree?

Answer 7

• 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

Question 8

why do we need to recreate the binary search tree periodically

Answer 8

• 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)