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].