Trees

Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this C++ DSA implementation can be compared directly with the rest of the DSA track.

node links A node stores one value plus references to its left and right children.

Basic Implementation

basic.cpp
Replay: real traced execution (multi-file project)
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
struct Node { int value; Node* left; Node* right; Node(int v, Node* l=nullptr, Node* r=nullptr): value(v), left(l), right(r) {} };
string render(Node* node) {
    if (node == nullptr) return "_";
    if (node->left == nullptr && node->right == nullptr) return to_string(node->value);
    return to_string(node->value) + "(" + render(node->left) + "," + render(node->right) + ")";
}
Node* sampleTree() {
    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}
string listString(const vector<int>& values) {
    stringstream out; out << "[";
    for (size_t i = 0; i < values.size(); i++) { if (i) out << ", "; out << values[i]; }
    out << "]"; return out.str();
}
int main() { cout << render(sampleTree()) << "\n"; }

  1. node ← 1, tree ← 1

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    13Node* sampleTree() {14    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));15}
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    1#include <iostream>2#include <queue>
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

Complexity

  • Time: O(n)
  • Space: O(n)

Implementation notes

  • In C++, each tree node is a struct Node with int value and raw Node* left / Node* right child links defaulting to nullptr.
  • sampleTree() builds the fixed shape with nested new Node(...) calls, wiring child pointers through constructor arguments rather than later assignments.
  • The source uses raw pointers, not smart pointers, and does not show a matching delete cleanup path for the seven allocated nodes.
  • The replay presents construction from leaves 1 and 3, to subtree 2(1,3), then 5, 7, subtree 6(5,7), and finally root 4(2(1,3),6(5,7)); it is a trace narrative, not a claim about sibling constructor-argument evaluation order.
  • render(Node*) returns _ for nullptr, a bare value for leaves, and recursive value(left,right) strings for internal nodes.
  • main streams render(sampleTree()) with std::cout << ... << "\n", producing 4(2(1,3),6(5,7)). Visible mutation is only the constructor wiring of raw child pointers during allocation.