Why am I getting a result opposite from what I expected?

Question

I wrote a code to figure out whether a small binary tree t1 is a subtree of t2. I am supposed to get true as the result but I am getting the opposite.

Here is my code:

class Node {
    int val;
    Node left, right;
    public Node(int v) {
        val = v;
        left = right = null;
    }
}
public class BT {
    Node root;
    public BT() {
        root = null;
    }
    public boolean containsTree(Node t1, Node t2) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        getOrderString(t1, s1);
        getOrderString(t2, s2);
        return s1.indexOf(s2.toString()) != -1;
    }
    public void getOrderString(Node t, StringBuilder s) {
        if (t == null) {
            s.append("X");
            return;
        }
        s.append(t.val);
        getOrderString(t.left, s);
        getOrderString(t.right, s);
    }
    public static void main(String[] args) {
        BT bt = new BT();
        bt.root = new Node(10);
        bt.root.left = new Node(12);
        bt.root.right = new Node(15);
        bt.root.left.left = new Node(25);
        bt.root.left.right = new Node(30);
        bt.root.right.left = new Node(36);
        BT bt2 = new BT();
        bt2.root = new Node(10);
        bt2.root.left = new Node(12);
        bt2.root.right = new Node(15);
        bt2.root.left.left = new Node(25);
        System.out.println(bt.containsTree(bt.root, bt2.root));
    }
}

Could anyone explain to me why i am getting false?

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Andy Turner, Feb 19 '20 at 20:18
You're getting false because it's not a subtree. Your first tree doesn't contain the second. — Andy Turner, Feb 19 '20 at 20:24

score 0 · Answer 1 · answered Feb 19 '20 at 20:32

Your API for constructing the tree is hard to read. If you defined a constructor:

public Node(int v, Node left, Node right)

Then you could declare your trees as:

bt.root = new Node(
    10,
    new Node(
        12,
        new Node(25, null, null),
        new Node(30, null, null)),
    new Node(
        25,
        new Node(36, null, null),
        null));

bt2.root = new Node(
    10,
    new Node(
        12,
        new Node(25, null, null),
        null)),
    new Node(15, null, null));

Like this, I think it is easy to see that the second isn't a subtree of the first:

the node with value 10 in the first has a right node with value 25; in the second it has a right value 15;
the node with value 12 in the first has a non-null right value, whereas it is null in the second.

score 0 · Accepted Answer · edited Jun 20 '20 at 09:12

0

2nd tree is not the subtree of 1st one. That's why it returns false so your code is actually correct :)

edited Jun 20 '20 at 09:12

Community

1
1

answered Feb 19 '20 at 20:38

emredmrcn

144
1
5

Why am I getting a result opposite from what I expected?

2 Answers2