Performance Improvement for Subtree for another tree

I was doing this algo on leetcode: https://leetcode.com/problems/subtree-of-another-tree/

Question: Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

For which I wrote this solution

var isSubtree = function(s, t) {
const reduceMainTreeToString = JSON.stringify(s)
const reduceGivenTreeToString = JSON.stringify(t)
if (reduceMainTreeToString.includes(reduceGivenTreeToString)) return true
else return false
};


I was super confident that it should be good performance and memory wise but unfortunately, I wasn't even able to cross 50% mark (though I was able to have 100% more memory efficient code).

This is how input s looks like

TreeNode {
val: 3,
right: TreeNode { val: 5, right: null, left: null },
left:
TreeNode {
val: 4,
right: TreeNode { val: 2, right: null, left: null },
left: TreeNode { val: 1, right: null, left: null } } }


And this is how input t looks like

TreeNode {
val: 4,
right: TreeNode { val: 2, right: null, left: null },
left: TreeNode { val: 1, right: null, left: null } }


This is the constructor:

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/


Can someone please suggest to me how I can improve the above code?

• Consider a main tree with a hundred thousand nodes, and a subtree of 3 nodes. It cannot be fast to access a hundred thousands nodes for no reason. Commented Nov 5, 2019 at 13:21
• Also, actually, can you provide us with the Constructor of Treenode? Commented Nov 5, 2019 at 16:26
• @konijn They haven't shared the constructor for the tree node. Commented Nov 5, 2019 at 16:33
• Its actually in comments on the site, added it to your question. Commented Nov 5, 2019 at 16:39

I was just about to post on your previous version of this question when you pulled it. As you have changed the code my old answer is mute apart from a few points;

The 100% memory efficient is the default value when leetcode has not collect the required minimum stats to provide comparative memory use.

The performance result can vary significantly submitting the very same code. Submit the code several times and you may get a much better score.

The snippet below completed in 62ms and was rated above 99.78% of JavaScript submissions. And got the bogus 100% memory score.

var isNodeEqual = function(a, b) {
const leftA = a.left !== null, leftB = b.left !== null;
const rightA = a.right !== null, rightB = b.right !== null;
if (leftA !== leftB || rightA !== rightB) { return false }
if ((leftA && a.left.val !== b.left.val) ||
(rightA && a.right.val !== b.right.val)) { return false }
return (leftA ? isNodeEqual(a.left, b.left) : true) &&
(rightA ? isNodeEqual(a.right, b.right) : true);
}
var isSubtree = function(s, t) {
const stack = [s];
while (stack.length) {
const node = stack.pop();
if (node.val === t.val && isNodeEqual(node, t)) { return true }
node.left !== null && stack.push(node.left);
node.right !== null &&  stack.push(node.right);
}
return false;
}


Rather than full recursion I used a stack to iterate the main tree, and recursion to test for matching sub tree.

I also avoided truthy and falsey statements as they introduced coercion overhead when testing for null or Object eg if(node.left) { is slower than if(node.left !== null) {

• Question, why does this code divisor < 0 && divisor = mod(divisor)  says invalid lefthand side in assignment and this does not node.left !== null && stack.push(node.left);. Here mod function just converts negative number to positive Commented Nov 26, 2019 at 11:59

A really short style review;

• var isSubtree = function( should be function isSubTree(, dont use flat arrow syntax unless you are declaring an inline function, or code golfing.
• You should only use stringify on the matching node, not the entire tree if you want to make this faster, though really you should avoid stringify altogether like Blindman69 if you want this code to be really fast.
• String.include already returns a boolean so

if (reduceMainTreeToString.includes(reduceGivenTreeToString)) return true else return false

becomes

return reduceMainTreeToString.includes(reduceGivenTreeToString);

this has the added advantage of not skipping curly braces in that if statement

I was in the middle of writing a rewrite, but Blindman67 beat me to it ;)