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.

Basic Implementation

basic.cpp 
#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"; }

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.
node links A node stores one value plus references to its left and right children.