Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA C++ - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a simple tree node struct with a value and pointers to children.

DSA C++

struct TreeNode {
    int val;
    TreeNode* [1];
};

Drag options to blanks, or click blank then click option'

Anext

Bchildren[2]

Cprev

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'next' or 'prev' which are used in linked lists, not trees.

A tree node typically has pointers to its children stored in an array or vector. Here, children[2] represents two child pointers.

2fill in blank

medium

Complete the code to traverse a binary tree in preorder (root, left, right).

DSA C++

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    std::cout << root->val << " ";
    preorder(root->[1]);
    preorder(root->children[1]);
}

Drag options to blanks, or click blank then click option'

Achildren[0]

Bleft

Cright

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'left' or 'right' when children array is used.

Using 'next' which is for linked lists.

In this tree structure, children[0] is the left child, so we traverse it after the root.

3fill in blank

hard

Fix the error in the code to insert a value into a binary search tree.

DSA C++

TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) {
        root = new TreeNode{val, [1];
        return root;
    }
    if (val < root->val) {
        root->children[0] = insert(root->children[0], val);
    } else {
        root->children[1] = insert(root->children[1], val);
    }
    return root;
}

Drag options to blanks, or click blank then click option'

A{nullptr, nullptr}

Bnullptr

C0

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using just nullptr which is not enough for an array of pointers.

Using empty braces {} which may not initialize children properly.

When creating a new node, both children pointers should be initialized to nullptr.

4fill in blank

hard

Fill both blanks to create a function that counts nodes in a binary tree.

DSA C++

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->[1]) + countNodes(root->[2]);
}

Drag options to blanks, or click blank then click option'

Achildren[0]

Bleft

Cchildren[1]

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'left' or 'right' when children array is used.

Forgetting to add 1 for the current node.

We count nodes by recursively counting left and right children, here represented by children[0] and children[1].

5fill in blank

hard

Fill all three blanks to create a function that finds the maximum value in a binary search tree.

DSA C++

int findMax(TreeNode* root) {
    if (root == nullptr) return INT_MIN;
    if (root->children[[1]] == nullptr) return root->val;
    return findMax(root->children[[2]]);
}

Drag options to blanks, or click blank then click option'

A0

B1

Attempts:

3 left

💡 Hint

Common Mistakes

Using left child index instead of right.

Not checking for nullptr before accessing children.

In a BST, the maximum value is found by going to the right child repeatedly, which is children[1].

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