import sys
import os
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), '..', '..'))

from utils.algo_context import AlgoContext
from utils.algo_array import Array
from vorlesung.L05_binaere_baeume.bin_tree import BinaryTree

ctx = AlgoContext()
values = Array.from_file('data/seq0.txt', ctx)
tree = BinaryTree(ctx)
for cell in values:
    tree.insert(cell.value)

# graph_traversal() erzeugt eine DOT-Datei und rendert sie als PDF.
# Die Datei landet im Verzeichnis, aus dem das Skript gestartet wird.
tree.graph_traversal()

# ── Antworten zu den Beobachtungsfragen ──────────────────────────────────────

# Welcher Knoten ist die Wurzel?
# Das erste eingefügte Element wird immer die Wurzel, da der Baum anfangs
# leer ist. Hier ist das -59 (erste Zeile von seq0.txt).
print("Wurzel:", tree.root.value)  # -59

# Wie viele Blattknoten hat der Baum?
# Ein Blattknoten hat weder ein linkes noch ein rechtes Kind.
blattknoten = []
def merke_blatt(node):
    if node.left is None and node.right is None:
        blattknoten.append(node.value)
tree.in_order_traversal(merke_blatt)
print("Blattknoten:", blattknoten)  # [-77, -50, 15, 48, 51, 58] → 6 Blätter

# Wie groß ist die Höhe des Baums?
# height() zählt rekursiv die längste Kante von der Wurzel zu einem Blatt.
# Mit 14 Elementen und zufälliger Reihenfolge ergibt sich hier Höhe 6.
print("Höhe:", tree.root.height())  # 6