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.c
Replay: real traced execution (multi-file project)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { int value; struct Node* left; struct Node* right; } Node;
Node* node_new(int value, Node* left, Node* right) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value; node->left = left; node->right = right; return node;
}
void append(char* out, const char* text) { strcat(out, text); }
void render(Node* node, char* out) {
    char buf[16];
    if (node == NULL) { append(out, "_"); return; }
    sprintf(buf, "%d", node->value); append(out, buf);
    if (node->left != NULL || node->right != NULL) {
        append(out, "("); render(node->left, out); append(out, ","); render(node->right, out); append(out, ")");
    }
}
Node* sample_tree(void) {
    return node_new(4, node_new(2, node_new(1, NULL, NULL), node_new(3, NULL, NULL)),
                       node_new(6, node_new(5, NULL, NULL), node_new(7, NULL, NULL)));
}
void print_list(int* values, int n) {
    printf("[");
    for (int i = 0; i < n; i++) { if (i) printf(", "); printf("%d", values[i]); }
    printf("]\n");
}
int main(void) { char out[128] = ""; render(sample_tree(), out); printf("%s\n", out); }

  1. node ← 1, tree ← 1

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step3node1, 3tree

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

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step2node2(1,3)tree

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

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step5node2(1,3), 5tree

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

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step7node2(1,3), 5, 7tree

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

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step6node2(1,3), 6(5,7)tree

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

    4typedef struct Node { int value; struct Node* left; struct Node* right; } Node;5Node* node_new(int value, Node* left, Node* right) {6    Node* node = (Node*)malloc(sizeof(Node));
    values this step4node4(2(1,3),6(5,7))tree

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

    12if (node == NULL) { append(out, "_"); return; }13sprintf(buf, "%d", node->value); append(out, buf);14if (node->left != NULL || node->right != NULL) {
    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

  • C defines typedef struct Node { int value; struct Node* left; struct Node* right; } Node, so each child link is a raw pointer or NULL.
  • node_new(int value, Node* left, Node* right) allocates one node with malloc(sizeof(Node)), writes the value and child pointers, and returns the owning pointer. This checked executable does not free the allocated nodes.
  • sample_tree() wires the fixed tree with nested node_new calls, passing NULL for leaf children and passing child pointers into their parent calls.
  • The replay presents construction leaf-to-root: 1, 3, 2(1,3), 5, 7, 6(5,7), then 4(2(1,3),6(5,7)).
  • render(Node* node, char* out) treats NULL as _, formats values with sprintf, and appends with strcat into main's stack buffer char out[128].
  • Visible memory is heap nodes plus the stack output buffer and temporary char buf[16]; visible pointer mutation happens inside node_new when it stores the left and right links.