Binary Search Tree

The video tutorial covers binary trees, focusing on binary search trees (BSTs). It explains the structure and properties of BSTs, emphasizing the importance of node arrangement where left subtree nodes are less than the root and right subtree nodes are greater. The tutorial distinguishes between balanced and unbalanced trees, highlighting their impact on computational complexity. It also details operations like searching, inserting, and deleting nodes in BSTs, explaining how these operations vary in complexity depending on tree balance.

What is a key characteristic of a Binary Search Tree (BST)?

• All nodes have exactly two children.

• Left subtree nodes are greater than the root.

• Right subtree nodes are less than the root.

• Left subtree nodes are less than the root.

What defines a balanced Binary Search Tree?

• The tree has equal number of nodes on both sides.

• The tree is perfectly symmetrical.

• The height difference between left and right subtrees is at most one.

• All nodes have two children.

How does the height of a balanced BST typically relate to the number of nodes?

• It is directly proportional to the number of nodes.

• It is quadratic in relation to the number of nodes.

• It is constant regardless of the number of nodes.

• It is logarithmic in relation to the number of nodes.

In a balanced BST, what is the time complexity of searching for an element?

• O(n)

• O(n^2)

• O(log n)

• O(1)

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

• O(1)

• O(log n)

• O(n)

• O(n^2)

Which operation in a BST can be the most complex due to multiple cases?

• Insertion

• Search

• Traversal

• Deletion

What happens to a BST when it becomes unbalanced?

• It becomes a complete tree.

• Its height becomes linear.

• Its operations become more efficient.

• Its height becomes logarithmic.

What is a potential consequence of repeated insertions in a BST?

• The tree's complexity becomes constant.

• The tree becomes more balanced.

• The tree becomes unbalanced.

• The tree's height decreases.

How can a balanced BST become unbalanced?

• By deleting nodes from one side only.

• By adding nodes symmetrically.

• By ensuring equal height on both sides.

• By maintaining a constant number of nodes.

What is the complexity of accessing a node in a balanced BST?

• O(1)

• O(n^2)

• O(log n)

• O(n)