Why BST Over Plain Binary Tree in DSA C - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of books and you want to organize them so you can find any book quickly. You can put them in any order (like a plain binary tree), or you can arrange them in a special order (like a Binary Search Tree) to find books faster.

🎯 Goal: Learn how to create a simple binary tree and a binary search tree (BST) with the same values, then see how searching is faster in BST because of its order.

📋 What You'll Learn

Create a plain binary tree with 5 nodes having values 10, 5, 15, 3, 7

Create a binary search tree (BST) with the same 5 values

Write a function to search for a value in both trees

Print the result of searching for value 7 in both trees

💡 Why This Matters

🌍 Real World

Organizing data so it can be found quickly is important in many apps like phone contacts, file systems, and databases.

💼 Career

Understanding BSTs helps in software development roles that involve data storage, search optimization, and algorithm design.

1

Create a plain binary tree with 5 nodes

Create a struct called Node with an int data and two pointers left and right. Then create 5 nodes with values 10, 5, 15, 3, and 7. Connect them to form a plain binary tree like this: root 10, left child 5, right child 15, left child of 5 is 3, right child of 5 is 7.

DSA C

# Define struct Node and create nodes with values 10, 5, 15, 3, 7
# Connect nodes to form the plain binary tree

Hint

Think of each node as a box holding a number and two arrows pointing to other boxes or nothing.

2

Create a binary search tree (BST) with the same values

Create a function insertBST that takes a Node* and an int value and inserts the value into the BST following BST rules (left child smaller, right child bigger). Use this function to insert values 10, 5, 15, 3, and 7 into a new BST root.

DSA C

#include 
#include 

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

Node* insertBST(Node* root, int value) {
    // Your code here
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 10;
    Node* node5 = (Node*)malloc(sizeof(Node));
    node5->data = 5;
    Node* node15 = (Node*)malloc(sizeof(Node));
    node15->data = 15;
    Node* node3 = (Node*)malloc(sizeof(Node));
    node3->data = 3;
    Node* node7 = (Node*)malloc(sizeof(Node));
    node7->data = 7;

    root->left = node5;
    root->right = node15;
    node5->left = node3;
    node5->right = node7;
    node15->left = NULL;
    node15->right = NULL;
    node3->left = NULL;
    node3->right = NULL;
    node7->left = NULL;
    node7->right = NULL;

    Node* bstRoot = NULL;
    // Insert values into BST
    // Your code here

    return 0;
}

Hint

Use recursion to find the right place to insert each value in the BST.

3

Write a function to search for a value in both trees

Write a function searchTree that takes a Node* and an int value and searches for the value in the plain binary tree using simple recursion (check current node, then left, then right). Also write a function searchBST that searches in the BST using BST rules (go left if value smaller, right if bigger).

DSA C

#include 
#include 

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

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node* insertBST(Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value data) {
        root->left = insertBST(root->left, value);
    } else {
        root->right = insertBST(root->right, value);
    }
    return root;
}

int searchTree(Node* root, int value) {
    // Your code here
}

int searchBST(Node* root, int value) {
    // Your code here
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 10;
    Node* node5 = (Node*)malloc(sizeof(Node));
    node5->data = 5;
    Node* node15 = (Node*)malloc(sizeof(Node));
    node15->data = 15;
    Node* node3 = (Node*)malloc(sizeof(Node));
    node3->data = 3;
    Node* node7 = (Node*)malloc(sizeof(Node));
    node7->data = 7;

    root->left = node5;
    root->right = node15;
    node5->left = node3;
    node5->right = node7;
    node15->left = NULL;
    node15->right = NULL;
    node3->left = NULL;
    node3->right = NULL;
    node7->left = NULL;
    node7->right = NULL;

    Node* bstRoot = NULL;
    bstRoot = insertBST(bstRoot, 10);
    bstRoot = insertBST(bstRoot, 5);
    bstRoot = insertBST(bstRoot, 15);
    bstRoot = insertBST(bstRoot, 3);
    bstRoot = insertBST(bstRoot, 7);

    return 0;
}

Hint

For plain tree, check all nodes. For BST, use the order to skip parts.

4

Print the result of searching for value 7 in both trees

Use printf to print "Found in plain tree" if searchTree(root, 7) returns 1, else "Not found in plain tree". Then print "Found in BST" if searchBST(bstRoot, 7) returns 1, else "Not found in BST".

DSA C

#include 
#include 

// ... previous code ...

int main() {
    // ... previous code ...

    if (searchTree(root, 7)) {
        // Your code here
    } else {
        // Your code here
    }

    if (searchBST(bstRoot, 7)) {
        // Your code here
    } else {
        // Your code here
    }

    return 0;
}

Hint

Use printf to show if the value 7 is found in each tree.

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching operations?

easy

A. Because BST does not require pointers to child nodes

B. Because BST uses less memory than a plain Binary Tree

C. Because BST nodes can have more than two children

D. Because BST keeps elements in a sorted order allowing faster search

Solution

1. Step 1: Understand the structure of BST

   A BST stores elements so that left child nodes are smaller and right child nodes are larger than the parent node, maintaining sorted order.

2. Step 2: Compare search efficiency

   This sorted structure allows searching by comparing values and moving left or right, reducing search time to O(log n) on average, unlike a plain Binary Tree which has no order and requires O(n) time.

3. Final Answer:

   Because BST keeps elements in a sorted order allowing faster search -> Option D

4. Quick Check:

   BST sorted order = faster search [OK]

Hint: BST is sorted, plain tree is not, so search is faster [OK]

Common Mistakes:

• Thinking BST uses less memory than plain tree
• Confusing number of children in BST
• Assuming BST nodes don't have child pointers

2. Which of the following is the correct way to declare a node structure for a BST in C?

easy

A. typedef struct Node { int data; struct Node* left; struct Node* right; } Node;

B. typedef struct Node { int data; struct Node left; struct Node right; } Node;

C. typedef struct Node { int data; Node* left; Node* right; } Node;

D. typedef struct Node { int data; int* left; int* right; } Node;

Solution

1. Step 1: Understand C struct pointer usage

   In C, to refer to the same struct type inside itself, pointers must be used with 'struct Node*'.

2. Step 2: Check each option

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; correctly uses 'struct Node*' for left and right pointers. typedef struct Node { int data; struct Node left; struct Node right; } Node; incorrectly uses struct Node (not pointer), causing infinite size. typedef struct Node { int data; Node* left; Node* right; } Node; uses 'Node*' without 'struct' keyword which is invalid in C without typedef. typedef struct Node { int data; int* left; int* right; } Node; uses int pointers which is incorrect for child nodes.

3. Final Answer:

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; -> Option A

4. Quick Check:

   Use 'struct Node*' for child pointers in C [OK]

Hint: Use 'struct Node*' for child pointers in C structs [OK]

Common Mistakes:

• Using struct Node instead of pointer causing infinite size
• Omitting 'struct' keyword in C
• Using int* instead of struct pointers

3. What will be the output of the following C code that inserts values into a BST and then performs an inorder traversal?

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

Node* insert(Node* root, int val) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = val;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    Node* root = NULL;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    inorder(root);
    return 0;
}

medium

A. 5 10 15

B. 10 5 15

C. 15 10 5

D. 10 15 5

Solution

1. Step 1: Trace insertions into BST

   Insert 10 as root. Insert 5 goes to left of 10. Insert 15 goes to right of 10.

2. Step 2: Perform inorder traversal

   Inorder visits left subtree, root, then right subtree. So it prints 5, then 10, then 15.

3. Final Answer:

   5 10 15 -> Option A

4. Quick Check:

   Inorder traversal of BST = sorted order [OK]

Hint: Inorder traversal of BST prints sorted values [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Not inserting nodes correctly
• Printing nodes in wrong order

4. The following code is intended to insert a value into a BST but causes a segmentation fault. What is the error?

Node* insert(Node* root, int val) {
    if (root == NULL) {
        Node newNode;
        newNode.data = val;
        newNode.left = NULL;
        newNode.right = NULL;
        return &newNode;
    }
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

medium

A. Not checking if root is NULL before accessing root->data

B. Using 'newNode' instead of 'newNode*' for pointer

C. Returning address of local variable 'newNode' which goes out of scope

D. Missing malloc to allocate memory for new node

Solution

1. Step 1: Analyze node creation in insert function

   The code creates 'Node newNode;' as a local variable on stack inside the function.

2. Step 2: Understand scope and pointer return

   Returning '&newNode' returns address of local variable which is destroyed after function returns, causing invalid memory access and segmentation fault.

3. Final Answer:

   Returning address of local variable 'newNode' which goes out of scope -> Option C

4. Quick Check:

   Local variable address returned = invalid pointer [OK]

Hint: Never return address of local variable; use malloc [OK]

Common Mistakes:

• Ignoring local variable lifetime
• Not using malloc for dynamic allocation
• Confusing pointer and value types

5. You have a plain Binary Tree and a BST both containing the same 7 unique integer values. Which of the following statements about searching for a value is TRUE?

hard

A. Searching in BST is always faster because it is balanced

B. Searching in BST can be faster on average due to ordered structure, but worst-case can be as slow as plain Binary Tree

C. Searching in plain Binary Tree is faster because it has no order constraints

D. Searching speed is the same for both because they have same number of nodes

Solution

1. Step 1: Understand BST search complexity

   BST search is O(log n) on average if balanced, but can degrade to O(n) if skewed.

2. Step 2: Compare with plain Binary Tree search

   Plain Binary Tree has no order, so search is always O(n) as it may need to check all nodes.

3. Step 3: Analyze given statements

   Searching in BST is always faster because it is balanced is false because BST is not always balanced. Searching in BST can be faster on average due to ordered structure, but worst-case can be as slow as plain Binary Tree correctly states average case advantage and worst case equality. Searching in plain Binary Tree is faster because it has no order constraints is false; plain tree is slower. Searching speed is the same for both because they have same number of nodes is false; structure affects search speed.

4. Final Answer:

   Searching in BST can be faster on average due to ordered structure, but worst-case can be as slow as plain Binary Tree -> Option B

5. Quick Check:

   BST average faster, worst-case equal [OK]

Hint: BST average faster, worst-case can be slow [OK]

Common Mistakes:

• Assuming BST is always balanced
• Thinking plain tree search is faster
• Ignoring worst-case BST behavior