Binary Tree Node Structure in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a Simple Binary Tree

What is the output of the inorder traversal for the given binary tree?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    inorder(root);
    return 0;
}

A 5 10 15

B 15 10 5

C 10 5 15

D 10 15 5

💡 Hint

Inorder traversal visits left child, then node, then right child.

Inorder traversal prints nodes in ascending order for binary search trees. Here, left child 5 is printed first, then root 10, then right child 15.

❓ Predict Output

intermediate

Output of Preorder Traversal on a Binary Tree

What is the output of the preorder traversal for the given binary tree?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void preorder(Node* root) {
    if (!root) return;
    std::cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

int main() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    preorder(root);
    return 0;
}

A 20 10 30

B 20 30 10

C 30 20 10

D 10 20 30

💡 Hint

Preorder traversal visits node first, then left child, then right child.

Preorder traversal prints root first, then left subtree, then right subtree. So output is '20 10 30 '.

❓ Predict Output

advanced

Output of Postorder Traversal on a Binary Tree

What is the output of the postorder traversal for the given binary tree?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    std::cout << root->data << " ";
}

int main() {
    Node* root = new Node(7);
    root->left = new Node(3);
    root->right = new Node(9);
    postorder(root);
    return 0;
}

A 3 7 9

B 7 3 9

C 9 7 3

D 3 9 7

💡 Hint

Postorder traversal visits left child, right child, then node.

Postorder traversal prints left subtree, right subtree, then root. So output is '3 9 7 '.

❓ Predict Output

advanced

Output of Level Order Traversal on a Binary Tree

What is the output of the level order traversal (breadth-first) for the given binary tree?

DSA C++

#include <iostream>
#include <queue>

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

void levelOrder(Node* root) {
    if (!root) return;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        std::cout << curr->data << " ";
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    levelOrder(root);
    return 0;
}

A 1 3 2 5 4

B 4 5 2 3 1

C 1 2 3 4 5

D 2 1 3 4 5

💡 Hint

Level order visits nodes level by level from left to right.

Level order traversal prints nodes level-wise: root first, then children from left to right. Output is '1 2 3 4 5 '.

🧠 Conceptual

expert

Number of Nodes in a Complete Binary Tree of Height h

What is the maximum number of nodes in a complete binary tree of height h (where height is the number of edges from root to deepest leaf)?

A 2^(h+1)

B 2^(h+1) - 1

C 2^h - 1

D 2^h

💡 Hint

A complete binary tree is full except possibly the last level, which is filled from left to right.

A complete binary tree of height h has at most 2^(h+1) - 1 nodes because each level i has up to 2^i nodes, summing to this formula.