Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA C++ - See It Work

Why Trees Exist and What Linked Lists and Arrays Cannot Do

📖 Scenario: Imagine you are organizing a family reunion. You want to keep track of family members and their relationships. Using just a list or an array makes it hard to show who is whose parent or child. Trees help us organize such hierarchical data clearly.

🎯 Goal: Build a simple tree structure in C++ to represent family relationships and see why linked lists and arrays cannot easily show these connections.

📋 What You'll Learn

Create a simple tree node structure with a name and pointers to children

Add a root node representing the grandparent

Add two children nodes representing the children of the grandparent

Print the family tree showing the grandparent and their children

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees, file systems, and organizational charts.

💼 Career

Understanding trees helps in software development tasks like building menus, databases, and search algorithms.

1

Create the Tree Node Structure

Write a struct called TreeNode with a string member called name and two TreeNode* members called left and right. Initialize left and right to nullptr.

DSA C++

// Your code here

Hint

Think of TreeNode as a box holding a name and two pointers to other boxes (children).

2

Create the Root Node

Create a TreeNode variable called grandparent and set its name to "Grandparent".

DSA C++

#include 
#include 
using namespace std;

struct TreeNode {
    string name;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};

// Your code here

Hint

Think of grandparent as the top box in your family tree.

3

Add Children to the Root Node

Create two TreeNode variables called parent1 and parent2. Set their name to "Parent1" and "Parent2" respectively. Then set grandparent.left to point to &parent1 and grandparent.right to point to &parent2.

DSA C++

#include 
#include 
using namespace std;

struct TreeNode {
    string name;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};

int main() {
    TreeNode grandparent;
    grandparent.name = "Grandparent";

    // Create two children nodes and link them to grandparent
    // Your code here

    return 0;
}

Hint

Each child is a box connected to the grandparent box by pointers.

4

Print the Family Tree

Print the grandparent.name, then print grandparent.left->name and grandparent.right->name on separate lines.

DSA C++

#include 
#include 
using namespace std;

struct TreeNode {
    string name;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};

int main() {
    TreeNode grandparent;
    grandparent.name = "Grandparent";

    TreeNode parent1;
    parent1.name = "Parent1";
    TreeNode parent2;
    parent2.name = "Parent2";

    grandparent.left = &parent1;
    grandparent.right = &parent2;

    // Print the family tree names
    // Your code here

    return 0;
}

Hint

Use cout and the arrow operator -> to access child names.

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees always provide faster access than arrays and linked lists

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees can represent hierarchical relationships which arrays and linked lists cannot

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data in a linear order, which makes it hard to represent hierarchical or branching relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow each element to have multiple children, representing hierarchical data like family trees or file systems.

3. Final Answer:

   Trees represent hierarchical relationships which arrays and linked lists cannot -> Option D

4. Quick Check:

   Hierarchical data needs trees = Because trees can represent hierarchical relationships which arrays and linked lists cannot [OK]

Hint: Trees model hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Assuming trees are simpler to implement
• Believing trees always have faster access

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

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

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

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

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

Solution

1. Step 1: Understand pointer usage in tree nodes

   Each child node should be a pointer to allow dynamic linking and avoid infinite size.

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

   struct Node { int data; Node* left; Node* right; }; uses pointers for both left and right child nodes, which is correct. Options A, B, and C mix pointers and objects incorrectly.

3. Final Answer:

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

4. Quick Check:

   Child nodes must be pointers = struct Node { int data; Node* left; Node* right; }; [OK]

Hint: Child nodes are pointers to avoid infinite size [OK]

Common Mistakes:

• Declaring child nodes as objects causing infinite recursion
• Mixing pointers and objects incorrectly
• Forgetting to use pointers for children

3. Consider this C++ code snippet for a binary tree node and insertion:

struct Node {
  int data;
  Node* left;
  Node* right;
  Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(15);
root->left->left = new Node(3);

std::cout << root->left->left->data << std::endl;

What will be the output?

medium

A. 5

B. 3

C. 10

D. 15

Solution

1. Step 1: Trace the tree construction

   Root node has value 10. Left child is 5, right child is 15. Left child's left child is 3.

2. Step 2: Identify the printed value

   The code prints root->left->left->data, which is the left child of 5, value 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   root->left->left = 3 [OK]

Hint: Follow pointers step-by-step to find value [OK]

Common Mistakes:

• Confusing left and right children
• Printing root->left->data instead of left->left
• Assuming default values instead of assigned

4. The following code tries to create a binary tree node but causes a compilation error. What is the error?

struct Node {
  int data;
  Node left;
  Node right;
  Node(int val) : data(val) {}
};

int main() {
  Node root(10);
  return 0;
}

medium

A. Error due to missing initialization of left and right nodes

B. Error because constructor syntax is wrong

C. Error because Node contains objects of its own type causing infinite size

D. No error, code compiles fine

Solution

1. Step 1: Analyze struct member types

   Node contains members left and right of type Node (not pointers), causing recursive embedding.

2. Step 2: Understand compilation error cause

   This recursive embedding causes infinite size, which is not allowed by the compiler.

3. Final Answer:

   Error because Node contains objects of its own type causing infinite size -> Option C

4. Quick Check:

   Struct with own type members causes infinite size error [OK]

Hint: Use pointers for self-referential structs to avoid infinite size [OK]

Common Mistakes:

• Thinking constructor syntax is wrong
• Assuming missing initialization causes error
• Believing code compiles fine

5. You want to represent a company's organizational chart where each manager can have multiple direct reports. Why is a tree a better choice than arrays or linked lists for this structure?

hard

A. Because trees allow multiple children per node, representing multiple reports naturally

B. Because arrays can only store numbers, not objects

C. Because linked lists cannot store hierarchical data at all

D. Because trees use less memory than arrays and linked lists

Solution

1. Step 1: Understand the organizational chart structure

   Each manager can have multiple direct reports, which is a hierarchical relationship with branching.

2. Step 2: Compare data structures for representing hierarchy

   Arrays and linked lists are linear and cannot naturally represent multiple children per node, but trees can.

3. Final Answer:

   Trees allow multiple children per node, representing multiple reports naturally -> Option A

4. Quick Check:

   Multiple children per node = trees [OK]

Hint: Multiple children per node? Use trees [OK]

Common Mistakes:

• Thinking arrays cannot store objects
• Believing linked lists cannot store any hierarchy
• Assuming trees always use less memory