BST Property and Why It Matters in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the BST property?

In a Binary Search Tree (BST), for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

beginner

Why does the BST property matter?

It allows fast searching, inserting, and deleting because we can decide to go left or right at each node, reducing the work to about log₂(n) steps.

intermediate

What happens if the BST property is broken?

The tree loses its order, making search and other operations slower, often requiring checking many nodes instead of just a few.

beginner

How does the BST property help in searching for a value?

At each node, compare the value to search with the node's value. If smaller, go left; if larger, go right. This halves the search space each step.

intermediate

Can a BST have duplicate values? Why or why not?

Usually no, because duplicates break the strict ordering needed for the BST property. Some variations allow duplicates but handle them carefully (e.g., always to the right).

What must be true for every node in a BST?

A Left subtree values < node < right subtree values

B Left subtree values > node > right subtree values

C All subtree values are equal to node

D No specific order is required

The BST property requires left subtree values to be smaller and right subtree values to be larger than the node.

Why is searching faster in a BST compared to a regular binary tree?

A Because BST property lets us ignore half the tree at each step

B Because BST is always balanced

C Because BST stores values in arrays

D Because BST uses hashing

The BST property lets us decide to go left or right, ignoring half the nodes each time, speeding up search.

What happens if you insert a value smaller than the root in a BST?

A It goes to the right subtree

B It goes to the left subtree

C It replaces the root

D It is ignored

Smaller values go to the left subtree to maintain the BST property.

If a BST property is broken, what is the likely effect?

A Tree becomes balanced

B Search becomes faster

C Search becomes slower

D Tree becomes empty

Breaking the BST property means we cannot decide direction easily, making search slower.

Which of these is NOT a reason the BST property is useful?

A Faster search

B Faster insert

C Faster delete

D Allows duplicate values anywhere

BST property usually does not allow duplicates anywhere; duplicates must be handled carefully.

Explain the BST property and how it helps in searching for a value.

Think about how you decide to go left or right when searching.

Describe what happens if the BST property is broken and why it matters.

Consider how the tree behaves without the ordering rule.