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

BST Property and Why It Matters

📖 Scenario: You are working with a simple phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. To keep the phone book efficient, you need to understand and use the BST property.

🎯 Goal: Build a small BST with three contacts and verify the BST property by checking the values of the nodes. This will help you understand why the BST property is important for fast searching.

📋 What You'll Learn

Create a struct called Node with an integer phoneNumber and two pointers left and right

Create three nodes with phone numbers 5551234, 5555678, and 5550000

Link the nodes to form a BST where 5551234 is the root, 5550000 is the left child, and 5555678 is the right child

Print the phone numbers of the root, left child, and right child to verify the BST structure

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and many databases use BSTs to organize data for quick search and retrieval.

💼 Career

Understanding BSTs is essential for software engineers working on efficient data storage, search algorithms, and system design.

1

Create the Node struct and three nodes

Create a struct called Node with an integer phoneNumber and two pointers left and right. Then create three Node variables called root, leftChild, and rightChild with phone numbers 5551234, 5550000, and 5555678 respectively.

DSA C++

// Define Node struct and create three nodes with given phone numbers
// Your code here

Hint

Define the struct with the three members. Then create the three nodes with the exact phone numbers given.

2

Link the nodes to form a BST

Link the nodes by setting root.left to &leftChild and root.right to &rightChild to form a BST where the root has the left and right children.

DSA C++

#include 

struct Node {
    int phoneNumber;
    Node* left;
    Node* right;
};

int main() {
    Node root = {5551234, nullptr, nullptr};
    Node leftChild = {5550000, nullptr, nullptr};
    Node rightChild = {5555678, nullptr, nullptr};
    // Link the nodes to form the BST
    // Your code here
    return 0;
}

Hint

Assign the addresses of leftChild and rightChild to root.left and root.right respectively.

3

Check the BST property by printing node values

Print the phone numbers of root, root.left, and root.right using std::cout to verify the BST structure.

DSA C++

#include 

struct Node {
    int phoneNumber;
    Node* left;
    Node* right;
};

int main() {
    Node root = {5551234, nullptr, nullptr};
    Node leftChild = {5550000, nullptr, nullptr};
    Node rightChild = {5555678, nullptr, nullptr};

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

    // Print the phone numbers of root, left child, and right child
    // Your code here
    return 0;
}

Hint

Use std::cout to print the phone numbers. Access the left and right child phone numbers using the arrow operator ->.

4

Run and verify the output

Run the program and verify that the output shows the root phone number as 5551234, the left child as 5550000, and the right child as 5555678.

DSA C++

#include 

struct Node {
    int phoneNumber;
    Node* left;
    Node* right;
};

int main() {
    Node root = {5551234, nullptr, nullptr};
    Node leftChild = {5550000, nullptr, nullptr};
    Node rightChild = {5555678, nullptr, nullptr};

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

    std::cout phoneNumber phoneNumber << std::endl;

    // Verify output
    // Your code here
    return 0;
}

Hint

Run the program and check the console output matches the expected phone numbers in order.