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.cs
Replay: real traced execution (multi-file project)
using System;
using System.Collections.Generic;
using System.Linq;

class Node {
    public int Value;
    public Node? Left;
    public Node? Right;
    public Node(int value, Node? left = null, Node? right = null) { Value = value; Left = left; Right = right; }
}
class Program {
    static string Render(Node? node) {
        if (node == null) return "_";
        if (node.Left == null && node.Right == null) return node.Value.ToString();
        return $"{node.Value}({Render(node.Left)},{Render(node.Right)})";
    }
    static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    static void Main() { Console.WriteLine(Render(SampleTree())); }
}

  1. node ← 1, tree ← 1

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step3node1, 3tree

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

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step2node2(1,3)tree

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

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step5node2(1,3), 5tree

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

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step7node2(1,3), 5, 7tree

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

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step6node2(1,3), 6(5,7)tree

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

    16}17static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    values this step4node4(2(1,3),6(5,7))tree

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

    18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { Console.WriteLine(Render(SampleTree())); }20}
    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

  • Render tree structure explicitly instead of printing node objects.
  • Node is a class, so each new Node(...) creates a managed reference object owned by the CLR and reclaimed by GC. The constructor defaults Node? left and Node? right to null, making absent children explicit in the object graph even when the canonical tree fills every leaf position in the render.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.