Create a Binary Tree Manually in DSA C++ - Build from Scratch

Create a Binary Tree Manually

📖 Scenario: You are building a simple binary tree to represent a family tree. Each node will hold a person's name as a string. You will create the tree manually by linking nodes together.

🎯 Goal: Build a binary tree manually by creating nodes and linking them as left and right children. Then print the tree nodes in preorder traversal.

📋 What You'll Learn

Create a struct called Node with a string data and two Node* pointers called left and right

Create three nodes with data "Grandparent", "Parent", and "Child"

Link the nodes so that Grandparent is the root, Parent is the left child of Grandparent, and Child is the right child of Parent

Write a function void preorder(Node* root) that prints the nodes in preorder (root, left, right)

Call preorder with the root node and print the names separated by spaces

💡 Why This Matters

🌍 Real World

Binary trees are used in many areas like family trees, decision trees, and organizing data hierarchically.

💼 Career

Understanding how to create and traverse trees is fundamental for software development, especially in areas like databases, compilers, and AI.

1

Create the Node struct and three nodes

Create a struct called Node with a string data and two Node* pointers called left and right. Then create three nodes called grandparent, parent, and child with data "Grandparent", "Parent", and "Child" respectively. Initialize their left and right pointers to nullptr.

DSA C++

#include 
#include 

using namespace std;

int main() {

    // Create struct Node and three nodes here

    return 0;
}

Hint

Define the struct outside main(). Initialize pointers to nullptr.

2

Link the nodes to form the tree

Link the nodes so that grandparent.left points to &parent and parent.right points to &child.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string data;
    Node* left;
    Node* right;
};

int main() {
    Node grandparent = {"Grandparent", nullptr, nullptr};
    Node parent = {"Parent", nullptr, nullptr};
    Node child = {"Child", nullptr, nullptr};

    // Link nodes here

    return 0;
}

Hint

Use the address-of operator & to link nodes.

3

Write a preorder traversal function

Write a function called void preorder(Node* root) that prints the data of the node, then recursively calls itself on the left child, then on the right child. Use cout to print the data followed by a space.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string data;
    Node* left;
    Node* right;
};

void preorder(Node* root) {
    // Print root data and recursively call preorder on left and right
    // Your code here
}

int main() {
    Node grandparent = {"Grandparent", nullptr, nullptr};
    Node parent = {"Parent", nullptr, nullptr};
    Node child = {"Child", nullptr, nullptr};

    grandparent.left = &parent;
    parent.right = &child;

    return 0;
}

Hint

Check if root is nullptr to stop recursion. Print root->data then call preorder on left and right.

4

Call preorder and print the tree

Call the preorder function with the address of grandparent and print a newline after the traversal.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string data;
    Node* left;
    Node* right;
};

void preorder(Node* root) {
    if (root == nullptr) return;
    cout data left);
    preorder(root->right);
}

int main() {
    Node grandparent = {"Grandparent", nullptr, nullptr};
    Node parent = {"Parent", nullptr, nullptr};
    Node child = {"Child", nullptr, nullptr};

    grandparent.left = &parent;
    parent.right = &child;

    // Call preorder with &grandparent and print newline
    // Your code here

    return 0;
}

Hint

Call preorder(&grandparent) and then print endl.