BST Property and Why It Matters in DSA Javascript - 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 than the node's value.

beginner

Why does the BST property matter?

It allows fast searching, insertion, and deletion because we can decide to go left or right at each node, reducing the search space quickly.

intermediate

What happens if the BST property is violated?

The tree no longer guarantees efficient search operations, and it behaves like a regular binary tree, losing the speed advantage.

beginner

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

At each node, compare the target value 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? How does the property handle them?

Usually, BSTs do not allow duplicates or store duplicates consistently (e.g., all duplicates go to the right). The property must be maintained to keep order.

What does the BST property ensure about the left subtree of a node?

A All values are smaller than the node's value

B All values are larger than the node's value

C Values can be any number

D All values are equal to the node's value

The BST property states that all values in the left subtree must be smaller than the node's value.

Why is the BST property important for search operations?

A It makes the tree balanced automatically

B It stores values in random order

C It allows skipping half of the tree at each step

D It prevents insertion of new nodes

Because the BST property lets us decide to go left or right, we skip half the nodes each time, making search faster.

If a node's value is 10, which subtree can contain the value 15?

A Left subtree

B None

C Either subtree

D Right subtree

Values larger than 10 must be in the right subtree according to the BST property.

What happens if the BST property is broken?

A Tree becomes balanced

B Search becomes slower

C Insertion is faster

D Tree becomes empty

Breaking the BST property means we can't efficiently decide which subtree to search, slowing down operations.

How are duplicates usually handled in a BST?

A Duplicates are not allowed or placed consistently (e.g., always right)

B Duplicates go to the left subtree

C Duplicates replace the node

D Duplicates are ignored

BSTs typically disallow duplicates or store them in a consistent subtree to maintain the property.

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

Think about how you decide which way to go when searching.

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

Consider the impact on search speed.