JavaScript में दो BST में टू सम

समस्या:

हमें एक JavaScript फ़ंक्शन लिखना है जो दो बाइनरी सर्च ट्री की जड़ों, root1 और root2, को पहले और दूसरे आर्गुमेंट के रूप में लेता है। फ़ंक्शन का तीसरा आर्गुमेंट संख्या target है।

हमारे फ़ंक्शन को True वापस करना चाहिए यदि और केवल यदि पहले ट्री में एक नोड और दूसरे ट्री में एक नोड है जिनके मान दिए गए पूर्णांक टारगेट तक जुड़ते हैं, अन्यथा false।

उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -

const target = 23;

BSTs

तो आउटपुट होना चाहिए -

const output = true;

आउटपुट व्याख्या:

क्योंकि पहले ट्री में 6 और दूसरे में 17 मौजूद है, जिनका योग 23 है।

उदाहरण

इसके लिए कोड होगा -

class Node{ 
  constructor(data) { 
    this.data = data; 
    this.left = null; 
    this.right = null; 
  }; 
}; 
class BinarySearchTree{ 
  constructor(){ 
    this.root = null; 
  } 
  insert(data){ 
    var newNode = new Node(data); 
    if(this.root === null){ 
      this.root = newNode; 
    }else{ 
      this.insertNode(this.root, newNode); 
    }; 
  }; 
  insertNode(node, newNode){ 
    if(newNode.data < node.data){ 
      if(node.left === null){ 
        node.left = newNode; 
      }else{ 
        this.insertNode(node.left, newNode); 
      }; 
    } else { 
      if(node.right === null){ 
        node.right = newNode; 
      }else{ 
        this.insertNode(node.right,newNode); 
      }; 
    }; 
  }; 
}; 
const tree1 = new BinarySearchTree(); 
tree1.insert(1); 
tree1.insert(3); 
tree1.insert(4); 
tree1.insert(2); 
tree1.insert(4); 
tree1.insert(5); 
tree1.insert(6); 
const tree2 = new BinarySearchTree(); 
tree2.insert(9); 
tree2.insert(6); 
tree2.insert(11); 
tree2.insert(3); 
tree2.insert(8); 
tree2.insert(10); 
tree2.insert(17); 
const twoSumBSTs = (root1, root2, target) => { 
  if(root1 == null || root2 == null) return false; 
  if(root1.data + root2.data == target) return true; 
  if(root1.data + root2.data < target) { 
    return twoSumBSTs(root1.right, root2, target) || twoSumBSTs(root1, root2.right, target); 
  }else{ 
    return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1, root2.left, target); 
  }; 
}; 
const target = 23; 
console.log(twoSumBSTs(tree1.root, tree2.root, target));

आउटपुट

कंसोल में आउटपुट होगा -

true