BST Property and Why It Matters in DSA C - Build from Scratch

BST Property and Why It Matters

📖 Scenario: Imagine you are organizing a library's book collection. To find any book quickly, you decide to arrange them in a special way: all books with titles alphabetically before a certain book go to the left shelf, and all books with titles after go to the right shelf. This is similar to how a Binary Search Tree (BST) works.

🎯 Goal: You will create a simple Binary Search Tree (BST) with three nodes and check if it follows the BST property. This will help you understand why the BST property is important for fast searching.

📋 What You'll Learn

Create a struct for a BST node with an integer value and pointers to left and right children.

Manually create three nodes with values 10, 5, and 15.

Link the nodes to form a BST where 5 is left child of 10 and 15 is right child of 10.

Write a function to check if the tree satisfies the BST property.

Print the result of the BST property check.

💡 Why This Matters

🌍 Real World

BSTs are used in databases, file systems, and many applications where quick search, insert, and delete operations are needed.

💼 Career

Understanding BSTs is fundamental for software developers, especially those working with data structures, algorithms, and performance optimization.

1

Create BST nodes with values

Create a struct called Node with an int value and two pointers left and right to Node. Then create three Node variables called root, leftChild, and rightChild with values 10, 5, and 15 respectively.

DSA C

// Define struct Node
// Create root, leftChild, rightChild nodes with values 10, 5, 15
// Your code here

Hint

Start by defining the Node struct with an integer and two pointers. Then create three variables of type Node with the exact values.

2

Link nodes to form BST

Link the leftChild as the left pointer of root and rightChild as the right pointer of root.

DSA C

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

Node root = {10, NULL, NULL};
Node leftChild = {5, NULL, NULL};
Node rightChild = {15, NULL, NULL};

// Link leftChild to root->left and rightChild to root->right
// Your code here

Hint

Use the address-of operator & to assign the addresses of leftChild and rightChild to root.left and root.right.

3

Write function to check BST property

Write a function called isBST that takes a pointer to Node called node, and two integers min and max. It returns 1 if the subtree rooted at node satisfies the BST property (all values are between min and max), otherwise returns 0. Use recursion to check left and right subtrees with updated ranges.

DSA C

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

Node root = {10, NULL, NULL};
Node leftChild = {5, NULL, NULL};
Node rightChild = {15, NULL, NULL};

root.left = &leftChild;
root.right = &rightChild;

// Write int isBST(Node* node, int min, int max) function
// Your code here

Hint

Check if the current node is NULL (empty), then return 1 (true). Otherwise, check if the node's value is within the allowed range. Recursively check left subtree with max as current node's value and right subtree with min as current node's value.

4

Print BST property check result

Print the result of calling isBST on &root with min as -1000 and max as 1000. Use printf to print "BST property holds: %d\n" with the result.

DSA C

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

Node root = {10, NULL, NULL};
Node leftChild = {5, NULL, NULL};
Node rightChild = {15, NULL, NULL};

root.left = &leftChild;
root.right = &rightChild;

int isBST(Node* node, int min, int max) {
    if (node == NULL) {
        return 1;
    }
    if (node->value value >= max) {
        return 0;
    }
    return isBST(node->left, min, node->value) && isBST(node->right, node->value, max);
}

// Print the result of isBST(&root, -1000, 1000)
// Your code here

Hint

Use printf to print the result of isBST(&root, -1000, 1000). The output should be BST property holds: 1 if the tree is a valid BST.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. All leaf nodes are at the same depth.

B. Each node has exactly two children.

C. Nodes are arranged in a complete binary tree structure.

D. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

Solution

1. Step 1: Understand BST definition

   A BST is defined by the order property where left subtree nodes are smaller and right subtree nodes are larger than the current node.

2. Step 2: Compare options with BST property

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches the BST property exactly. Other options describe different tree types or properties.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option D

4. Quick Check:

   BST property = left < node < right [OK]

Hint: Remember BST orders left < node < right [OK]

Common Mistakes:

• Confusing BST with complete binary tree
• Thinking all nodes must have two children
• Assuming leaf nodes must be at same depth

2. Which of the following is the correct syntax to check if a node's left child value is less than the node's value in C?

easy

A. if (node->left->value < node->value) {}

B. if (node.left.value < node.value) {}

C. if (node->left.value < node->value) {}

D. if (node.left->value < node.value) {}

Solution

1. Step 1: Understand C struct pointer access

   In C, to access a member of a struct pointer, use '->'. So node->left accesses left child pointer.

2. Step 2: Check each option for correct pointer syntax

   if (node->left->value < node->value) {} uses node->left->value correctly. Others mix '.' and '->' incorrectly.

3. Final Answer:

   if (node->left->value < node->value) {} -> Option A

4. Quick Check:

   Use '->' for pointer members in C [OK]

Hint: Use '->' to access struct pointer members in C [OK]

Common Mistakes:

• Using '.' instead of '->' for pointers
• Mixing '.' and '->' incorrectly
• Forgetting to check if left child is NULL before access

3. Given the following BST insertion code snippet in C, what will be the inorder traversal output after inserting values 10, 5, 15, 3, 7?

medium

A. [15, 10, 7, 5, 3]

B. [10, 5, 15, 3, 7]

C. [3, 5, 7, 10, 15]

D. [5, 3, 7, 10, 15]

Solution

1. Step 1: Insert values into BST following property

   Insert 10 as root, 5 left of 10, 15 right of 10, 3 left of 5, 7 right of 5.

2. Step 2: Perform inorder traversal (left, node, right)

   Inorder visits nodes in ascending order: 3, 5, 7, 10, 15.

3. Final Answer:

   [3, 5, 7, 10, 15] -> Option C

4. Quick Check:

   Inorder traversal of BST = sorted values [OK]

Hint: Inorder traversal of BST gives sorted order [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Inserting nodes incorrectly violating BST property
• Reading traversal output in insertion order

4. Consider this C code snippet for BST insertion. What is the error?

void insert(Node** root, int val) {
  if (*root == NULL) {
    *root = malloc(sizeof(Node));
    (*root)->value = val;
    (*root)->left = NULL;
    (*root)->right = NULL;
  } else if (val < (*root)->value) {
    insert(&(*root)->left, val);
  } else {
    insert(&(*root)->right, val);
  }
}

medium

A. Missing check for duplicate values before insertion.

B. No error; code correctly inserts into BST.

C. Incorrect use of pointer to pointer for root parameter.

D. Memory allocation size should be sizeof(Node*), not sizeof(Node).

Solution

1. Step 1: Analyze insertion logic for duplicates

   The code inserts values less than current node to left, else to right, so duplicates go right without check.

2. Step 2: Identify missing duplicate check

   BST usually avoids duplicates or handles them explicitly; this code lacks that check.

3. Final Answer:

   Missing check for duplicate values before insertion. -> Option A

4. Quick Check:

   Duplicates need explicit handling in BST insert [OK]

Hint: Check for duplicates before inserting in BST [OK]

Common Mistakes:

• Assuming duplicates are allowed without check
• Confusing pointer usage in recursive calls
• Incorrect malloc size for struct allocation

5. You have a BST where the property is violated at one node: the right child has a smaller value than the parent. How does this violation affect searching for a value larger than the parent in the BST?

hard

A. Search will always return the parent node regardless of the value.

B. Search may fail or return incorrect results because the BST property is broken.

C. Search will be faster because smaller values on right reduce search space.

D. Search will still work correctly because only one node is wrong.

Solution

1. Step 1: Understand BST property importance in search

   BST search relies on left < node < right property to decide which subtree to explore.

2. Step 2: Analyze effect of violation on search

   If right child is smaller, search for larger values may wrongly go left or miss nodes, causing failure or wrong results.

3. Final Answer:

   Search may fail or return incorrect results because the BST property is broken. -> Option B

4. Quick Check:

   BST property violation breaks search correctness [OK]

Hint: BST property must hold for correct search [OK]

Common Mistakes:

• Assuming one violation doesn't affect search
• Thinking search speed improves with violation
• Believing search always returns parent node