Cannot figure out logic flaw in traversal to check whether a tree has a particular subtree within it

What a fun question!

const empty =
  {}

const tree = (v = null, l = empty, r = empty) =>
  ({ v, l, r })

We need two trees, t1 and t2 -

t1:
     3
    / \
   4   5
  / \
 1   2

t2:
   4
  / \
 1   2

We can easily write those using tree -

const t1 =
  tree
    ( 3
    , tree(4, tree(1), tree(2))
    , tree(5)
    )

const t2 =
  tree(4, tree(1), tree(2))

I think you have the right idea for testing if two trees are equal -

1. If both t1 and t2 are empty, there is nothing left to compare, return true
2. By induction, both t1 and t2 are not empty. If t1 xor t2 is empty, return false
3. By induction, neither t1 nor t2 are empty. If t1.v matches t2.v, recur and compare each subtree

const equal = (t1 = empty, t2 = empty) =>
  t1 === empty && t2 === empty
    ? true                       // 1
: t1 === empty || t2 === empty
    ? false                      // 2
: t1.v === t2.v                  // 3
    && equal(t1.l, t2.l)
    && equal(t2.l, t2.r)

We can write isSubTree -

1. When t is empty, s is a subtree of t if s is empty
2. By induction, t is not empty. return equal(t,s) or recur on t.l or recur on t.r

const isSubTree = (t = empty, s = empty) =>
  t === empty
    ? s === empty          // 1
    : equal(t, s)          // 2
      || isSubTree(t.l, s)
      || isSubTree(t.r, s)

See the code in action! Verify the results in your own browser below -

const empty =
  {}

const tree = (v = null, l = empty, r = empty) =>
  ({ v, l, r })

const equal = (t1 = empty, t2 = empty) =>
  t1 === empty && t2 === empty
    ? true
: t1 === empty || t2 === empty
    ? false
: t1.v === t2.v
    && equal(t1.l, t2.l)
    && equal(t1.r, t2.r)

const isSubTree = (t = empty, s = empty) =>
  t === empty
    ? s === empty
    : equal(t, s)
      || isSubTree(t.l, s)
      || isSubTree(t.r, s)

const t1 =
  tree
    ( 3
    , tree(4, tree(1), tree(2))
    , tree(5)
    )

const t2 =
  tree(4, tree(1), tree(2))

const t3 =
  tree(4, tree(1), tree(9))

console.log(isSubTree(t1, t2)) // true
console.log(isSubTree(t1, t3)) // false

I hope that this approach shows you that sometimes less is more when it comes to writing programs.

boolean logic

This question has a good opportunity to start learning about boolean logic. If you're like me, you don't like writing conditionals like -

if (someCondition)
  return true
else
  return false

return someCondition ? true : false

Since someCondition is already a boolean, in both cases it's more straightforward to write -

return someCondition

When we wrote equal, we see we are returning true and false in some of the code branches. But it's not exactly easy to see how these can be cleaned up...

const equal = (t1 = empty, t2 = empty) =>
  // can we collapse the explicit bools?
  t1 === empty && t2 === empty
    ? true                       // <-- explicit bool
: t1 === empty || t2 === empty
    ? false                      // <-- explicit bool
: t1.v === t2.v
    && equal(t1.l, t2.l)
    && equal(t1.r, t2.r)

We're don't want to be reckless and guess which logic is correct. We will approach this methodically using a truth table so we can get a reliable answer -

│ p := (t1 === empty)
│ q := (t2 === empty)

┌───┬───┬──────────┬───────────┬─────────┬──────────┬──────────┬───────────┐
│ p │ q │ p 'and q │ p 'nand q │ p 'or q │ p 'nor q │ p 'xor q │ p 'xnor q │
├───┼───┼──────────┼───────────┼─────────┼──────────┼──────────┼───────────┤
│ 1 │ 1 │    1     │     0     │    1    │    0     │    0     │     1     │
│ 1 │ 0 │    0     │     1     │    1    │    0     │    1     │     0     │
│ 0 │ 1 │    0     │     1     │    1    │    0     │    1     │     0     │
│ 0 │ 0 │    0     │     1     │    0    │    1     │    0     │     1     │
└───┴───┴──────────┴───────────┴─────────┴──────────┴──────────┴───────────┘

Referencing our truth table, we can see that and and nor perfectly describe our boolean logic -

const equal = (t1 = empty, t2 = empty) =>
                                 //┌───┬───┬┬──────────┬──────────┐
                                 //│ p │ q ││ p 'and q │ p 'nor q │
                                 //├───┼───┼┼──────────┼──────────┤
  t1 === empty && t2 === empty   
    ? true                       //│ 1 │ 1 ││    1     │    0     │

: t1 === empty || t2 === empty   
    ? false                      //│ 1 │ 0 ││    0     │    0     │
                                 //│ 0 │ 1 ││    0     │    0     │

                                 //│ 0 │ 0 ││    0     │    1     │
: t1.v === t2.v                  //└───┴───┴┴──────────┴──────────┘
    && equal(t1.l, t2.l)         
    && equal(t1.r, t2.r)   

Use of and matches the top two conditions and code branches; nor matches the final branch where we recur -

const nor = (x, y) =>
  !(Boolean(x) || Boolean(y))

const equal = (t1 = empty, t2 = empty) =>
                                  //┌───┬───┬┬──────────┬──────────┐
                                  //│ p │ q ││ p 'and q │ p 'nor q │
                                  //├───┼───┼┼──────────┼──────────┤
  nor(t1 === empty, t2 === empty) //│ 0 │ 0 ││    0     │    1     │
    ? t1.v === t2.v
        && equal(t1.l, t2.l)
        && equal(t1.r, t2.r)
    : t1 === empty && t2 === empty//│ 1 │ 0 ││    0     │    0     │
                                  //│ 0 │ 1 ││    0     │    0     │
                                  //│ 1 │ 1 ││    1     │    0     │

Or in plain words -

1. If neither tree is empty, the trees are equal if the value matches and the subtrees are equal
2. By induction, at least one tree is empty. The trees are equal only if both trees are empty.

const equal = (t1 = empty, t2 = empty) =>
  nor(t1 === empty, t2 === empty)
    ? t1.v === t2.v                 // 1
        && equal(t1.l, t2.l)
        && equal(t1.r, t2.r)
    : t1 === empty && t2 === empty  // 2

NB we call nor before and (&&). This is because we only want to recur when neither tree is empty. Because and and nor return the same answer for (p = 1, q = 0) and (p = 0, q = 1), we can only make recursion exclusive on the nor branch by putting it first.

isSameTree looks OK to me. isSubTree is hard to follow, but basically all you have to do is walk s and run isSameTree for every subtree rooted at each node in s. If at any point in isSubtree we find that one or the other node is null, we need to check that they're both null before assuming success, which is the same logic needed in equalTrees.

There is room for improvement in efficiency--this seems to be O(st) where for every node in s, we check every node in t. The LeetCode thread has interesting optimizations including Merkle hashing and checking the max depth of each tree and only running comparisons on the one possible level where subtrees could match from. There are also stringification solutions.

const equalTrees = (s, t) => {
  if (!s || !t) return s === t;
  
  return s.val === t.val && 
         equalTrees(s.left, t.left) &&
         equalTrees(s.right, t.right);
};

const isSubtree = (s, t) => {
  if (!s || !t) return s === t;
  
  return equalTrees(s, t) || 
         isSubtree(s.left, t) || 
         isSubtree(s.right, t);
};

const a = {
  val: 1,
  left: {
    val: 2,
    right: {val: 3}
  },
  right: {
    val: 4,
    left: {val: 5},
    right: {val: 6}
  }
};
const b = {
  val: 4,
  left: {val: 5},
  right: {val: 6}
};
const c = {
  val: 4,
  left: {val: 42}, // wrong val
  right: {val: 6}
};
const d = {
  val: 4,
  left: {val: 5},
  right: {
    val: 6,
    left: {val: 7} // extra child
  }
};

console.log(isSubtree(a, b));
console.log(isSubtree(a, c));
console.log(isSubtree(a, d));

After looking at the comments above I have come up with the following solution:

const isSubtree = (s, t) => {
    if (!s) return false
    if (!t) return true
    if (s.val === t.val) {
        if (isSameTree(s, t)) return true
    }
    return isSubtree(s.left, t) || isSubtree(s.right, t)
}

const isSameTree = (c, t) => {
    if (!c && !t) return true
    if (!c || !t) return false
    if (c.val !== t.val) return false
    return isSameTree(c.left, t.left) && isSameTree(c.right, t.right)
}