Binary Search Tree

Question 1

In what order is the node retrieved using Pre-order Traversal?

Answer 1

Root-Left-Right

Question 2

In what order is the node retrieved using In-order Traversal?

Answer 2

Left-Root-Right

Question 3

In what order is the node retrieved 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 follow the left child, if more 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 follow the left child, if more follow 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 is the minimum possible height of a BST for n number of nodes?

Answer 6

square root(n+1)

Question 7

What is a binary tree?

Answer 7

A binary tree is a tree where each node has at most two children.

The two children of a node are commonly referred to as the left child and the right child of the node

Question 8

What is a binary search tree?

Answer 8

A binary search tree is a binary tree in which all values smaller than a node are stored in that node’s left subtree and all values larger than a node are stored in that node’s right subtree

Question 9

How can an unbalanced binary tree be rebalanced?

Answer 9

The binary search tree needs to be re-created or rebalanced with the same items to make it balanced

Question 10

What are the advantages of Binary Search Tree? (3 in total)

Answer 10

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.

Insertion and deletion of items involves the updating of pointers instead of rearranging elements, making the operations much more efficient, especially when the data stored in each entry is large

Question 11

What are the disadvantages of Binary Search Tree?

Answer 11

• Nodes of BST cannot be accessed by index
• BST may become unbalanced in the course of usage, making binary search of the tree inefficient because the time complexity of binary search becomes almost O(n) instead of O(lg n) requires balancing to maintain optimal performance

Question 12

What is an unbalanced binary search tree?

Answer 12

A binary search tree is unbalanced when one side of the tree has many more elements/nodes than the other side

Question 13

Why is an unbalanced binary tree disadvantageous?

Answer 13

This makes binary search of the binary search tree inefficient
because the time complexity of binary search becomes almost O(n) instead of O(lg n)