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 Java 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.java
Replay: real traced execution (multi-file project)
import java.util.*;

public class Basic {
    static class Node {
        int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
    }
    static String render(Node node) {
        if (node == null) return "_";
        if (node.left == null && node.right == null) return Integer.toString(node.value);
        return node.value + "(" + render(node.left) + "," + render(node.right) + ")";
    }
    static Node sampleTree() {
        return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    }
    public static void main(String[] args) { System.out.println(render(sampleTree())); }
}

  1. node ← 1, tree ← 1

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step3node1, 3tree

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

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step2node2(1,3)tree

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

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step5node2(1,3), 5tree

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

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step7node2(1,3), 5, 7tree

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

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step6node2(1,3), 6(5,7)tree

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

    16static Node sampleTree() {17    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));18}
    values this step4node4(2(1,3),6(5,7))tree

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

    18    }19    public static void main(String[] args) { System.out.println(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

  • Java represents each tree node as a Node object with primitive int value plus Node left and Node right reference fields. The one-argument constructor leaves child references at their default null value.
  • sampleTree() wires the tree with nested constructor calls: new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7))). Java evaluates those arguments left to right, matching the replay order that creates leaves before their parents.
  • The two-argument-child constructor stores existing node object references into left and right; no queue, list, or builder structure is involved.
  • render checks node == null for missing children, prints leaf values directly, and recursively formats internal nodes as value(left,right). The allocated Node objects and render-time strings are normal JVM heap objects managed by GC after printing 4(2(1,3),6(5,7)).