Binary Search Trees

Question 1

What is a Binary Search Tree ?

Answer 1

The left subtree of a node contains values less than the node’s value,
The right subtree of a node contains values greater than the node’s value.

Question 2

What is the height and size of a BST ?

Answer 2

Height = The longest path from the root to a leaf,
Size = The total number of nodes in a tree.

Question 3

How are BSTs constructed ?

Answer 3

If the new value is less than the curerent node, move to the left subtree,
If the value is greater, move it to the right.

Question 4

How to do a BST search ?

Answer 4

Start from the root,
Move left or right based on comparisons,
O(log n)

Question 5

How to do a BST insertion ?

Answer 5

Locate the appropriate leaf node,
insert as a new leaf,
O(log n)

Question 6

How to do a BST deletion ?

Answer 6

The node to delete may have:
No Children - simply remove,
One Child - Replace the node with its child,
Two Children - replace with left or right child,
O(log n)

Question 7

What is an AVL tree ?

Answer 7

A self balancing tree that uses rotations to ensure that the height difference between left and right subtrees is, at most, 1.

Question 8

What are the AVL tree rotations ?

Answer 8

Left rotation (Right-Right imbalance),
Right rotation (Left-Left imbalance),
Left-Right rotation (Left-right imbalance),
Right-Left rotation (Right-left imbalance.