13. Binary trees and BST

public class TreeNode(int val) { public int Val = val; public TreeNode? Left, Right; }

// Depth-first traversals
static void InOrder(TreeNode? n, List<int> o) { if (n is null) return; InOrder(n.Left, o); o.Add(n.Val); InOrder(n.Right, o); }  // BST → sorted
static void PreOrder(TreeNode? n, List<int> o) { if (n is null) return; o.Add(n.Val); PreOrder(n.Left, o); PreOrder(n.Right, o); }

// Height / max depth
static int Height(TreeNode? n) => n is null ? 0 : 1 + Math.Max(Height(n.Left), Height(n.Right));

// Level-order (BFS) with a queue
static List<List<int>> Levels(TreeNode? root)
{
    var result = new List<List<int>>();
    if (root is null) return result;
    var q = new Queue<TreeNode>(); q.Enqueue(root);
    while (q.Count > 0)
    {
        var level = new List<int>();
        for (int size = q.Count; size > 0; size--)
        {
            var n = q.Dequeue(); level.Add(n.Val);
            if (n.Left is not null) q.Enqueue(n.Left);
            if (n.Right is not null) q.Enqueue(n.Right);
        }
        result.Add(level);
    }
    return result;
}

// Validate BST using bounds
static bool IsBst(TreeNode? n, long min = long.MinValue, long max = long.MaxValue) =>
    n is null || (n.Val > min && n.Val < max && IsBst(n.Left, min, n.Val) && IsBst(n.Right, n.Val, max));