BST Property and Why It Matters in DSA Typescript - 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 for searching?

Because the BST property keeps smaller values to the left and larger to the right, it allows fast searching by deciding which subtree to explore next, reducing the search space quickly.

beginner

How does the BST property help in inserting a new value?

When inserting, the BST property guides where to place the new value by comparing it with nodes, moving left if smaller or right if larger, ensuring the tree stays ordered.

intermediate

What happens if the BST property is violated?

If the BST property is broken, searching and inserting become inefficient because the tree loses its order, possibly turning into a list and slowing operations to linear time.

beginner

Explain the BST property using a real-life example.

Think of a phone book sorted by names: all names starting with A come before B, and so on. This order helps you quickly find a name by skipping large sections, just like BST property helps find values fast.

What must be true for every node in a BST?

A All values in left and right subtrees are equal

B Left subtree values are larger, right subtree values are smaller

C Left subtree values are smaller, right subtree values are larger

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 does the BST property improve search speed?

A It stores values randomly

B It allows skipping half of the tree at each step

C It duplicates values for faster access

D It uses a queue to find values

Because values are ordered, you can decide to go left or right, skipping half the nodes each time.

If a new value is smaller than a node's value, where should it go in a BST?

A Left subtree

B Right subtree

C At the node itself

D Anywhere in the tree

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

What is a consequence of violating the BST property?

A Search and insert become slower

B Tree becomes balanced automatically

C Values get sorted faster

D No effect on operations

Violating the property can make the tree unorganized, slowing down operations.

Which real-life example best illustrates the BST property?

A A shuffled deck of cards

B A pile of unsorted papers

C A random list of names

D A sorted phone book

A sorted phone book helps find names quickly, similar to how BST property organizes values.

Describe the BST property and explain why it is important for efficient searching.

Think about how the tree guides you to find values quickly.

Explain what could happen if the BST property is not maintained in a tree.

Consider how the tree's structure affects speed.