Same InOrder Traversal

AreEqualsInOrderTraversal.cs

using System.Text;

static void Visit(TreeNode node, StringBuilder sb) => sb.Append(node.Id);

static TreeNode? Step(TreeNode node, HashSet<TreeNode> visited, Stack<TreeNode> stack, StringBuilder sb)
{
    if (node.Left is not null && !visited.Contains(node.Left))
    {
        stack.Push(node);
        return node.Left;
    }
    Visit(node, sb);
    visited.Add(node);
    if (node.Right is not null)
        return node.Right;

    while (stack.Count > 0)
    {
        node = stack.Pop();
        if (visited.Contains(node))
            continue;
        return node;
    }
    return null;
}

static bool CompareInOrder(TreeNode? n1, TreeNode? n2)
{
    if (n1 is null && n2 is null)
        return true;
    if (n1 is null || n2 is null)
        return false;

    Stack<TreeNode> s1 = [], s2 = [];
    HashSet<TreeNode> v1 = [], v2 = [];
    StringBuilder sb1 = new(), sb2 = new();
    while (n1 is not null || n2 is not null)
    {
        bool steppedIntoA = false, steppedIntoB = false;
        if (n1 is not null)
        {
            n1 = Step(n1, v1, s1, sb1);
            steppedIntoA = true;
        }

        if (n2 is not null)
        {
            n2 = Step(n2, v2, s2, sb2);
            steppedIntoB = true;
        }

        if (!steppedIntoA || !steppedIntoB) break;
    }

    Console.WriteLine(sb1);
    Console.WriteLine(sb2);
    return string.Compare(sb1.ToString(), sb2.ToString(), StringComparison.Ordinal) == 0;
}
TreeNode t1 = new('a', new('b', new('c', new('d', new('e', null, new('f'))))));
// TreeNode t2 = new('e', null, new('a', new('c', new('d', new('f')), new('b'))));
TreeNode t2 = new('e', null, new('b'));

Console.WriteLine(CompareInOrder(t1, t2));
(t1, t2) = (t2, t1);
Console.WriteLine(CompareInOrder(t1, t2));

sealed class TreeNode(char id, TreeNode? left = null, TreeNode? right = null)
{
    public char Id => id;
    public TreeNode? Left => left;
    public TreeNode? Right => right;

    public static explicit operator TreeNode(char c) => new(c);
    public static explicit operator char(TreeNode node) => node.Id;
    public override string ToString() => $"{Id}";
}