データ構造としての二分木を扱う際、その構造的な特性を分析する問題や、二分探索木（BST）の性質を活用した検索問題は頻出します。ここでは、ノードの値を無視した構造の対称性判定と、BST内で特定の値より小さい最大のノードを見つけるアルゴリズムを提示します。

構造的対称性の判定

この問題では、ノードに格納されたデータの値に関係なく、ツリーの形状が左右対称であるかを判定します。アプローチとして、ルートノードの左右の子ノードを比較する再帰関数を定義します。左側の部分木と右側の部分木が鏡像のような関係になっているかを確認するため、左ノードの左側と右ノードの右側、そして左ノードの右側と右ノードの左側をそれぞれ比較していきます。

class TreeUtil {
    // ノードの定義
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    // 構造が対称かどうかを判定するエントリーポイント
    public static boolean checkStructuralSymmetry(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    // 2つのノードの構造が鏡像であるかを再帰的に確認
    private static boolean isMirror(TreeNode t1, TreeNode t2) {
        // 両方がnullであれば構造は一致
        if (t1 == null && t2 == null) return true;
        // 片方のみがnullであれば構造は不一致
        if (t1 == null || t2 == null) return false;

        // 左ノードの左子 vs 右ノードの右子
        // 左ノードの右子 vs 右ノードの左子
        // の両方が一致していれば、現在の部分木は対称
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}

二分探索木における閾値未満の最大ノードの探索

二分探索木（BST）では、左の子ノードは親より小さく、右の子ノードは親より大きいという性質があります。この性質を利用して、指定された値 $x$ よりも小さい値を持つノードの中で最大のものを探索します。再帰的な実装も可能ですが、ここではパフォーマンスとスタックオーバーフローの回避を考慮して、反復的なアプローチ（whileループ）で実装します。

基本的なロジックは以下の通りです：

• 現在のノードの値が $x$ 以上の場合：解は必ず左部分木に存在するため、左へ移動します。
• 現在のノードの値が $x$ 未満の場合：このノードは解の候補です。しかし、右部分木にはこのノードより大きく、かつ $x$ 未満の値が存在する可能性があるため、現在のノードを候補として記録しつつ、右へ移動してより大きな候補を探します。

class BstSearcher {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 指定された値limitより小さい値を持つノードの中で最大のものを返します。
     * 該当するノードが存在しない場合はnullを返します。
     */
    public static TreeNode findMaxUnderLimit(TreeNode root, int limit) {
        TreeNode result = null;
        TreeNode current = root;

        while (current != null) {
            if (current.val < limit) {
                // 現在のノードは条件を満たすため、暫定的な結果として保持
                result = current;
                // より大きな（しかしlimit未満の）値を探すために右へ進む
                current = current.right;
            } else {
                // 現在のノードがlimit以上の場合、条件を満たす値は左側にあるはず
                current = current.left;
            }
        }
        return result;
    }
}