Equivalent sorted binary tree In Java

Issue

I am learning Go and in this tutorial, concurrency and channels can be used to complete this exercise: Solution.

And I try to solve this by Java. The solution I can think of is to use temporary data structure to store the results of the in-order traversal of these two trees, and then compare.

For example, I use a StringBuilder to store the result of the in-order traversal and then compare(Notice that we're comparing sorted binary trees):

    public boolean equivalentBST(TreeNode p, TreeNode q) {
        StringBuilder pSb = new StringBuilder();
        walk(pSb, p);
        StringBuilder qSb = new StringBuilder();
        walk(qSb, q);
        return pSb.compareTo(qSb) == 0;
    }

    private void walk(StringBuilder sb, TreeNode node) {
        if (node == null) {
            return;
        }
        walk(sb, node.left);
        sb.append(node.val);
        walk(sb, node.right);
    }

Testcase:

        TreeNode p = new TreeNode(9);
        TreeNode p2 = new TreeNode(8);
        TreeNode p3 = new TreeNode(7);
        p.left = p2;
        p2.left = p3;

        TreeNode q = new TreeNode(9);
        TreeNode q2 = new TreeNode(8);
        TreeNode q3 = new TreeNode(7);
        q3.right = q2;
        q.left = q3;

        System.out.println(equivalentBST(q, p)); // output true

I want to know is there any other better way to solve this by Java?

Solution

You can walk both trees at the same time and compare their elements immediately without using a StringBuilder.

Something along the lines:

public boolean equivalentBST(TreeNode node1, TreeNode node2) {
    var stack1 = new ArrayList<TreeNode>();
    var stack2 = new ArrayList<TreeNode>();

    while (true) {
        while (node1 != null) {
            stack1.add(node1);
            node1 = node1.left;
        }
        while (node2 != null) {
            stack2.add(node2);
            node2 = node2.left;
        }
        if (stack1.isEmpty() || stack2.isEmpty())
            return stack1.isEmpty() && stack2.isEmpty();
        node1 = stack1.remove(stack1.size() - 1);
        node2 = stack2.remove(stack2.size() - 1);
        if (node1.val != node2.val)
            return false;
        node1 = node1.right;
        node2 = node2.right;
    }
}

Answered By - ciamej