Im vorherigen Artikel habe ich eine Level-Order-Traversierung eines Binärbaums in Rust behandelt. Diesmal möchte ich ein klassisches Problem von LeetCode #98: Validate Binary Search Tree angehen.

Die Aufgabe verlangt von uns zu bestimmen, ob ein Binärbaum ein gültiger binärer Suchbaum (BST) ist. Damit ein Baum ein gültiger BST ist:

  • Der linke Teilbaum eines Knotens darf nur Werte enthalten, die kleiner sind als der Wert des Knotens.
  • Der rechte Teilbaum eines Knotens darf nur Werte enthalten, die größer sind als der Wert des Knotens.
  • Sowohl der linke als auch der rechte Teilbaum müssen selbst ebenfalls gültige BSTs sein.

Rust-Baumdarstellung

Das LeetCode-Problem definiert die Baumstruktur für uns. In Rust ist geteilte Ownership mit veränderbarem Zugriff knifflig, weshalb die gängige Darstellung Rc<RefCell<T>> verwendet.

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
  • Rc (Reference Counted) ermöglicht mehrere Besitzer desselben Baumknotens.
  • RefCell bietet Interior Mutability — sodass wir Knoten zur Laufzeit mutable ausleihen können.

Diese Kombination ist komplexer als das, was du in Sprachen wie Python oder Java sehen würdest, wo eine rekursive Lösung trivial wäre. Aber Rusts Ownership-Modell erzwingt Explizitheit und Sicherheit.

Iterative Validierung mit Grenzen

Die Schlüsselidee bei der Validierung eines BST ist die Bereichspropagierung. Für jeden Knoten muss sein Wert strikt zwischen einem min und max Grenzwert liegen.

  • Für die Wurzel sind die Grenzen (-∞, +∞).
  • Beim Gehen nach links wird das neue Maximum zum Wert des Elternknotens.
  • Beim Gehen nach rechts wird das neue Minimum zum Wert des Elternknotens.

Anstatt Rekursion können wir eine Queue (VecDeque) verwenden, um Knoten zusammen mit ihrem aktuellen gültigen Bereich zu verfolgen:

use std::collections::VecDeque;

struct Solution;

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let mut queue = VecDeque::new();
        queue.push_back((root.clone(), i64::MIN, i64::MAX));

        while let Some((Some(r), min, max)) = queue.pop_front() {
            // Laufzeit-Borrow-Check - panicked wenn bereits mutable ausgeliehen
            // Der Borrow wird automatisch am Ende dieses Scopes freigegeben
            let r = r.borrow();
            let r_val = r.val as i64;

            if !(min < r_val && r_val < max) {
                return false;
            }

            if r.left.is_some() {
                queue.push_back((r.left.clone(), min, r_val));
            }
            if r.right.is_some() {
                queue.push_back((r.right.clone(), r_val, max));
            }
        }

        true
    }
}

Warum VecDeque anstelle von Vec?

In Rust können sowohl Vec als auch VecDeque als Stacks zum Verwalten von Knoten während der Traversierung fungieren. Der Unterschied liegt in Semantik und Kosten:

  • Vec bietet O(1) push/pop am Ende, was es ideal für Tiefensuche (DFS) macht.
  • VecDeque bietet O(1) push/pop an beiden Enden, was es natürlicher für Breitensuche (BFS) macht.

In dieser Lösung machen wir konzeptionell eine Level-Order-Prüfung mit expliziten Grenzen, daher passt VecDeque zur Absicht: Es ermöglicht uns, Kinder hinten anzuhängen und vorne zu entnehmen, ohne umständliche Indizierungstricks.

Könnte man hier Vec verwenden? Absolut. Man würde einfach am Ende pushen und poppen und es effektiv in eine DFS statt einer BFS umwandeln. Der Algorithmus wäre immer noch korrekt, da die Reihenfolge der Knotenverarbeitung für die BST-Validierung keine Rolle spielt — jeder Knoten wird unabhängig gegen seinen Bereich geprüft.

Aber die Wahl von VecDeque ist eine Frage der Klarheit: Es macht den Traversierungsstil explizit und vermeidet Verwirrung bei Lesern darüber, ob der Algorithmus auf DFS-Reihenfolge angewiesen ist (ist er nicht).

Warum i64 für einen i32-Baum?

Beachte, dass wir Werte nach i64 casten. Dies vermeidet Overflow bei Edge Cases wie i32::MIN und i32::MAX. Ohne diese Erweiterung könnte die Grenzenpropagierung falsch umbrechen.

Warum Rekursion vermeiden?

Viele Lehrbuchlösungen verwenden Rekursion, aber in Rust sind iterative Lösungen oft sicherer und schneller:

  1. Stack-Wachstum Rekursive Aufrufe lassen den Programm-Call-Stack wachsen, der begrenzt ist. Bei großen Bäumen riskiert tiefe Rekursion einen Stack-Overflow. Iteration vermeidet dies vollständig.

  2. Performance Jeder rekursive Aufruf hat Overhead. Rust führt keine automatische Tail-Call-Optimierung durch, sodass Rekursion unnötige Funktionsaufruf-Frames verursachen kann. Iteration mit einer expliziten Queue (VecDeque) vermeidet das.

  3. Kontrolle über den Zustand Iteration ermöglicht die Verwaltung zusätzlicher Zustände (wie min/max-Bereiche) ohne Parameter durch rekursive Aufrufe zu fädeln. Das führt zu saubererem Rust-Code.

  4. Interior-Mutability-Überlegungen Die Verwendung von RefCell verschiebt die Borrow-Prüfung von der Kompilierzeit zur Laufzeit. Das führt zu leichten dynamischen Kosten, aber in der Praxis sind sie hier vernachlässigbar. Trotzdem bedeutet explizite Iteration, dass du genau weißt, wann Borrows genommen und freigegeben werden.

Komplexitätsanalyse

  • Zeitkomplexität: O(n), da jeder Knoten einmal besucht wird.
  • Speicherkomplexität: O(n), da im schlimmsten Fall die Queue alle Knoten einer Ebene halten kann.

Das ist identisch zu einem rekursiven Ansatz in asymptotischen Begriffen, vermeidet aber Call-Stack-Limitierungen.

Vergleich: Inorder-Traversierung-Ansatz

Ein alternativer Ansatz ist eine Inorder-Traversierung. In einem gültigen BST ist die Inorder-Sequenz streng monoton steigend. Man könnte den zuletzt besuchten Wert speichern und die Reihenfolge prüfen.

Das funktioniert, aber ich bevorzuge die explizite Bereichspropagierungsmethode: Sie vermeidet subtile Bugs (wie falsches Initialisieren von "previous") und passt natürlicher zu Rusts Ownership-Semantik.

Testfälle

Die klassischen Beispiele illustrieren sowohl gültige als auch ungültige BSTs.

#[cfg(test)]
mod tests {
    use super::*;

    /// ## Beispiel 1: Gültiger BST
    ///    2
    ///   / \
    ///  1   3
    #[test]
    fn case1() {
        let mut root = TreeNode::new(2);
        root.left = Some(Rc::new(RefCell::new(TreeNode::new(1))));
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));

        assert!(Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));
    }

    /// ## Beispiel 2: Ungültiger BST
    ///        5
    ///       / \
    ///      1   4
    ///         / \
    ///        3   6
    #[test]
    fn case2() {
        let mut root = TreeNode::new(5);
        root.left = Some(Rc::new(RefCell::new(TreeNode::new(1))));

        let mut right = TreeNode::new(4);
        right.left = Some(Rc::new(RefCell::new(TreeNode::new(3))));
        right.right = Some(Rc::new(RefCell::new(TreeNode::new(6))));

        root.right = Some(Rc::new(RefCell::new(right)));

        assert!(!Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));
    }

    /// ## Edge Cases
    /// - Einzelknoten-Baum mit `i32::MIN`
    /// - Ungültiger Baum, bei dem rechtes Kind gleich Eltern ist
    #[test]
    fn case_edge_values() {
        // Einzelner Knoten mit i32::MIN ist gültig
        let root = TreeNode::new(i32::MIN);
        assert!(Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));

        // Ungültig, weil rechtes Kind gleich Eltern ist
        let mut root = TreeNode::new(i32::MAX);
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(i32::MAX))));
        assert!(!Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));
    }
}

Fazit

Dieses Problem ist ein gutes Beispiel dafür, wie rekursive Lehrbuchlösungen nicht immer gut zu Rust passen. Indem wir den Zustand mit einer VecDeque explizit machen, vermeiden wir Stack-Overflows, reduzieren Overhead und behalten die volle Kontrolle über Ownership- und Borrowing-Regeln.

Beim Lösen algorithmischer Probleme in Rust solltest du immer hinterfragen, ob Rekursion das richtige Werkzeug ist — oft ist eine iterative Lösung sowohl sicherer als auch idiomatischer.