BST property and invariant in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BST stand for in data structures?

BST stands for Binary Search Tree, a type of tree data structure where each node has at most two children.

beginner

What is the main property of a Binary Search Tree (BST)?

In a BST, for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.

intermediate

Why is the BST property important?

The BST property allows efficient searching, insertion, and deletion operations by narrowing down the search path based on comparisons.

intermediate

What does the BST invariant ensure during tree operations?

The BST invariant ensures that after any insertion or deletion, the tree still maintains the BST property where left children are smaller and right children are larger than their parent nodes.

intermediate

Can duplicate values be stored in a BST according to the BST property?

Typically, BSTs do not allow duplicate values because the property requires strict less-than and greater-than relationships. Some variations handle duplicates by specific rules, but standard BSTs avoid them.

In a BST, where are values smaller than a node's value located?

A At the root only

B In the right subtree

C Anywhere in the tree

D In the left subtree

By definition, all values smaller than a node's value are found in its left subtree.

What must be true about the values in the right subtree of a BST node?

A They are smaller than the node's value

B They are greater than the node's value

C They are equal to the node's value

D They can be any value

The BST property requires all values in the right subtree to be greater than the node's value.

What does the BST invariant help maintain?

A The BST property after insertions and deletions

B The number of nodes

C The height of the tree

D The tree is balanced

The BST invariant ensures the BST property holds true after any changes to the tree.

Which operation benefits most from the BST property?

A Searching for a value

B Sorting a list

C Adding duplicates

D Reversing the tree

Searching is efficient in a BST because the property guides the search path.

Are duplicate values allowed in a standard BST?

A Only if they are in the right subtree

B Yes, always

C No, duplicates are not allowed

D Only if they are in the left subtree

Standard BSTs do not allow duplicates to maintain strict ordering.

Explain the BST property and why it is important for tree operations.

Think about how the tree organizes values to find them quickly.

Describe what the BST invariant means and how it affects insertion and deletion.

Consider what must stay true every time you add or remove a node.