3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – konijn Nov 5 '19 at 13:21
  • \$\begingroup\$ Also, actually, can you provide us with the Constructor of Treenode? \$\endgroup\$ – konijn Nov 5 '19 at 16:26
  • \$\begingroup\$ @konijn They haven't shared the constructor for the tree node. \$\endgroup\$ – iRohitBhatia Nov 5 '19 at 16:33
  • \$\begingroup\$ Its actually in comments on the site, added it to your question. \$\endgroup\$ – konijn Nov 5 '19 at 16:39
4
\$\begingroup\$

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) {

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – iRohitBhatia Nov 26 '19 at 11:59
2
\$\begingroup\$

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 ;)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.