Binary Search Tree

Question 1

What is a binary search tree?

Answer 1

Tree data structure in which each node has at most two children. Binary search trees are sorted, where the left child’s value is less than its parent and the right child’s value is greater than the parent.

Question 2

What are binary search trees good at?

Answer 2

Inserting and searching.

Question 3

What should the skeleton of a node class look like for BST?

Answer 3

it should have a value, left , and right property.

Question 4

What should the skeleton of a BST class look like?

Answer 4

It should just have a root property.

Question 5

What is the time complexity of searching for an element in a Binary Search Tree (BST)?

Answer 5

O(log n), where n is the number of elements in the BST.

Question 6

Briefly describe the process of searching for an element in a BST.

Answer 6

1 - Start at the root node.
2 - If the element you’re searching for is equal to the current node’s value, you’ve found it.
3 - If the element is less than the current node’s value, traverse to the left child.
4 - If the element is greater than the current node’s value, traverse to the right child.
5 - Repeat steps 2-4 until the element is found or you reach an empty child pointer, indicating the element doesn’t exist.

Question 7

What is the time complexity of inserting an element into a BST?

Answer 7

O(log n) in the average case, but can be O(n) in the worst case (e.g., inserting elements in sorted order).

Question 8

Briefly describe the process of inserting an element into a BST.

Answer 8

1 - Start at the root node.
2 - If the tree is empty, create a new node with the element and make it the root.
3 - If the element is less than the current node’s value, traverse to the left child.
4 - If the element is greater than the current node’s value, traverse to the right child.
5 - Repeat steps 2-4 until you reach an empty child pointer.
6 - Create a new node with the element and make it the child of the current node (left if less, right if greater).

Question 9

What property must hold true for a Binary Search Tree (BST) to be valid?

Answer 9

For any node, all elements in its left subtree must be less than the node’s value, and all elements in its right subtree must be greater than the node’s value.