Given a binary tree containing n distinct numbers and a value x. The problem is to count pairs in the given binary tree whose sum is equal to the given value x.
Examples:
Input :
5
/ \
3 7
/ \ / \
2 4 6 8
x = 10
Output : 3
The pairs are (3, 7), (2, 8) and (4, 6).
1) Naive Approach:
One by one get each node of the binary tree through any of the tree traversals methods. Pass the node say temp, the root of the tree and value x to another function say findPair(). In the function with the help of the root pointer traverse the tree again. One by one sum up these nodes with temp and check whether sum == x. If so, increment count. Calculate count = count / 2 as a single pair has been counted twice by the aforementioned method.
Implementation:
C++
// C++ implementation to count pairs in a binary tree// whose sum is equal to given value x#include <bits/stdc++.h>using namespace std;// structure of a node of a binary treestruct Node { int data; Node *left, *right;};// function to create and return a node// of a binary treeNode* getNode(int data){ // allocate space for the node Node* new_node = (Node*)malloc(sizeof(Node)); // put in the data new_node->data = data; new_node->left = new_node->right = NULL; return new_node;}// returns true if a pair exists with given sum 'x'bool findPair(Node* root, Node* temp, int x){ // base case if (!root) return false; // pair exists if (root != temp && ((root->data + temp->data) == x)) return true; // find pair in left and right subtrees if (findPair(root->left, temp, x) || findPair(root->right, temp, x)) return true; // pair does not exists with given sum 'x' return false;}// function to count pairs in a binary tree// whose sum is equal to given value xvoid countPairs(Node* root, Node* curr, int x, int& count){ // if tree is empty if (!curr) return; // check whether pair exists for current node 'curr' // in the binary tree that sum up to 'x' if (findPair(root, curr, x)) count++; // recursively count pairs in left subtree countPairs(root, curr->left, x, count); // recursively count pairs in right subtree countPairs(root, curr->right, x, count);}// Driver program to test aboveint main(){ // formation of binary tree Node* root = getNode(5); /* 5 */ root->left = getNode(3); /* / \ */ root->right = getNode(7); /* 3 7 */ root->left->left = getNode(2); /* / \ / \ */ root->left->right = getNode(4); /* 2 4 6 8 */ root->right->left = getNode(6); root->right->right = getNode(8); int x = 10; int count = 0; countPairs(root, root, x, count); count = count / 2; cout << "Count = " << count; return 0;}// This code is contributed by yash agarwal(yashagarwal2852002) |
Java
// Java implementation to count pairs in a binary tree// whose sum is equal to given value ximport java.util.*;class GFG{// structure of a node of a binary treestatic class Node { int data; Node left, right;};static int count;// function to create and return a node// of a binary treestatic Node getNode(int data){ // allocate space for the node Node new_node = new Node(); // put in the data new_node.data = data; new_node.left = new_node.right = null; return new_node;}// returns true if a pair exists with given sum 'x'static boolean findPair(Node root, Node temp, int x){ // base case if (root==null) return false; // pair exists if (root != temp && ((root.data + temp.data) == x)) return true; // find pair in left and right subtrees if (findPair(root.left, temp, x) || findPair(root.right, temp, x)) return true; // pair does not exists with given sum 'x' return false;}// function to count pairs in a binary tree// whose sum is equal to given value xstatic void countPairs(Node root, Node curr, int x){ // if tree is empty if (curr == null) return; // check whether pair exists for current node 'curr' // in the binary tree that sum up to 'x' if (findPair(root, curr, x)) count++; // recursively count pairs in left subtree countPairs(root, curr.left, x); // recursively count pairs in right subtree countPairs(root, curr.right, x);}// Driver codepublic static void main(String[] args){ // formation of binary tree Node root = getNode(5); /* 5 */ root.left = getNode(3); /* / \ */ root.right = getNode(7); /* 3 7 */ root.left.left = getNode(2); /* / \ / \ */ root.left.right = getNode(4); /* 2 4 6 8 */ root.right.left = getNode(6); root.right.right = getNode(8); int x = 10; count = 0; countPairs(root, root, x); count = count / 2; System.out.print("Count = " + count);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation to count pairs in a binary tree# whose sum is equal to given value x# structure of a node of a binary treeclass getNode(object): def __init__(self, value): self.data = value self.left = None self.right = None# returns True if a pair exists with given sum 'x'def findPair(root, temp, x): # base case if root == None: return False # pair exists if (root != temp and ((root.data + temp.data) == x)): return True # find pair in left and right subtrees if (findPair(root.left, temp, x) or findPair(root.right, temp, x)): return True # pair does not exists with given sum 'x' return False # function to count pairs in a binary tree# whose sum is equal to given value xdef countPairs(root, curr, x): global count # if tree is empty if curr == None: return # check whether pair exists for current node 'curr' # in the binary tree that sum up to 'x' if (findPair(root, curr, x)): count += 1 # recursively count pairs in left subtree countPairs(root, curr.left, x) # recursively count pairs in right subtree countPairs(root, curr.right, x)# Driver program to test above# formation of binary treeroot = getNode(5) root.left = getNode(3) root.right = getNode(7) root.left.left = getNode(2) root.left.right = getNode(4)root.right.left = getNode(6)root.right.right = getNode(8)x = 10count = 0countPairs(root, root, x)count = count // 2print("Count =", count)# This code is contributed by shubhamsingh10 |
C#
// C# implementation to count pairs in a binary tree// whose sum is equal to given value xusing System;class GFG{// structure of a node of a binary treeclass Node { public int data; public Node left, right;};static int count;// function to create and return a node// of a binary treestatic Node getNode(int data){ // allocate space for the node Node new_node = new Node(); // put in the data new_node.data = data; new_node.left = new_node.right = null; return new_node;}// returns true if a pair exists with given sum 'x'static bool findPair(Node root, Node temp, int x){ // base case if (root == null) return false; // pair exists if (root != temp && ((root.data + temp.data) == x)) return true; // find pair in left and right subtrees if (findPair(root.left, temp, x) || findPair(root.right, temp, x)) return true; // pair does not exists with given sum 'x' return false;}// function to count pairs in a binary tree// whose sum is equal to given value xstatic void countPairs(Node root, Node curr, int x){ // if tree is empty if (curr == null) return; // check whether pair exists for current node 'curr' // in the binary tree that sum up to 'x' if (findPair(root, curr, x)) count++; // recursively count pairs in left subtree countPairs(root, curr.left, x); // recursively count pairs in right subtree countPairs(root, curr.right, x);}// Driver codepublic static void Main(String[] args){ // formation of binary tree Node root = getNode(5); /* 5 */ root.left = getNode(3); /* / \ */ root.right = getNode(7); /* 3 7 */ root.left.left = getNode(2); /* / \ / \ */ root.left.right = getNode(4); /* 2 4 6 8 */ root.right.left = getNode(6); root.right.right = getNode(8); int x = 10; count = 0; countPairs(root, root, x); count = count / 2; Console.Write("Count = " + count);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation to count// pairs in a binary tree whose sum is// equal to given value x// Structure of a node of a binary treeclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }};var count = 0;// Function to create and return a node// of a binary treefunction getNode(data){ // Allocate space for the node var new_node = new Node(); // Put in the data new_node.data = data; new_node.left = new_node.right = null; return new_node;}// Returns true if a pair exists// with given sum 'x'function findPair(root, temp, x){ // Base case if (root == null) return false; // Pair exists if (root != temp && ((root.data + temp.data) == x)) return true; // Find pair in left and right subtrees if (findPair(root.left, temp, x) || findPair(root.right, temp, x)) return true; // Pair does not exists with given sum 'x' return false;}// Function to count pairs in a binary tree// whose sum is equal to given value xfunction countPairs( root, curr, x){ // If tree is empty if (curr == null) return; // Check whether pair exists for current node // 'curr' in the binary tree that sum up to 'x' if (findPair(root, curr, x)) count++; // Recursively count pairs in left subtree countPairs(root, curr.left, x); // Recursively count pairs in right subtree countPairs(root, curr.right, x);}// Driver code// Formation of binary treevar root = getNode(5); /* 5 */root.left = getNode(3); /* / \ */root.right = getNode(7); /* 3 7 */root.left.left = getNode(2); /* / \ / \ */root.left.right = getNode(4); /* 2 4 6 8 */root.right.left = getNode(6);root.right.right = getNode(8);var x = 10;count = 0;countPairs(root, root, x);count = parseInt(count / 2);document.write("Count = " + count);// This code is contributed by noob2000</script> |
Output
Count = 3
Time Complexity: O(n^2).
Auxiliary Space: O(1)
2) Efficient Approach: Following are the steps:
- Convert given binary tree to doubly linked list. Refer this post.
- Sort the doubly linked list obtained in Step 1. Refer this post.
- Count Pairs in sorted doubly linked with sum equal to ‘x’. Refer this post.
- Display the count obtained in Step 4.
Implementation:
C++
// C++ implementation to count pairs in a binary tree// whose sum is equal to given value x#include <bits/stdc++.h>using namespace std;// structure of a node of a binary treestruct Node { int data; Node *left, *right; Node(int val){ this->data = val; this->left = this->right = NULL; }};// A simple recursive function to convert a given// Binary tree to Doubly Linked List// root --> Root of Binary Tree// head_ref --> Pointer to head node of created// doubly linked listvoid BToDLL(Node* root, Node** head_ref){ // Base cases if (root == NULL) return; // Recursively convert right subtree BToDLL(root->right, head_ref); // insert root into DLL root->right = *head_ref; // Change left pointer of previous head if (*head_ref != NULL) (*head_ref)->left = root; // Change head of Doubly linked list *head_ref = root; // Recursively convert left subtree BToDLL(root->left, head_ref);}// Split a doubly linked list (DLL) into 2 DLLs of// half sizesNode* split(Node* head){ Node *fast = head, *slow = head; while (fast->right && fast->right->right) { fast = fast->right->right; slow = slow->right; } Node* temp = slow->right; slow->right = NULL; return temp;}// Function to merge two sorted doubly linked listsNode* merge(Node* first, Node* second){ // If first linked list is empty if (!first) return second; // If second linked list is empty if (!second) return first; // Pick the smaller value if (first->data < second->data) { first->right = merge(first->right, second); first->right->left = first; first->left = NULL; return first; } else { second->right = merge(first, second->right); second->right->left = second; second->left = NULL; return second; }}// Function to do merge sortNode* mergeSort(Node* head){ if (!head || !head->right) return head; Node* second = split(head); // Recur for left and right halves head = mergeSort(head); second = mergeSort(second); // Merge the two sorted halves return merge(head, second);}// Function to count pairs in a sorted doubly linked list// whose sum equal to given value xint pairSum(Node* head, int x){ // Set two pointers, first to the beginning of DLL // and second to the end of DLL. Node* first = head; Node* second = head; while (second->right != NULL) second = second->right; int count = 0; // The loop terminates when either of two pointers // become NULL, or they cross each other (second->right // == first), or they become same (first == second) while (first != NULL && second != NULL && first != second && second->right != first) { // pair found if ((first->data + second->data) == x) { count++; // move first in forward direction first = first->right; // move second in backward direction second = second->left; } else { if ((first->data + second->data) < x) first = first->right; else second = second->left; } } return count;}// function to count pairs in a binary tree// whose sum is equal to given value xint countPairs(Node* root, int x){ Node* head = NULL; int count = 0; // Convert binary tree to // doubly linked list BToDLL(root, &head); // sort DLL head = mergeSort(head); // count pairs return pairSum(head, x);}// Driver program to test aboveint main(){ // formation of binary tree Node* root = new Node(5); /* 5 */ root->left = new Node(3); /* / \ */ root->right = new Node(7); /* 3 7 */ root->left->left = new Node(2); /* / \ / \ */ root->left->right = new Node(4); /* 2 4 6 8 */ root->right->left = new Node(6); root->right->right = new Node(8); int x = 10; cout << "Count = " << countPairs(root, x); return 0;} |
Java
// Java implementation to count pairs // in a binary tree whose sum is equal to// given value xclass GFG { // structure of a node of a binary tree static class Node { int data; Node left, right; }; static Node head_ref; // function to create and return a node // of a binary tree static Node getNode(int data) { // allocate space for the node Node new_node = new Node(); // put in the data new_node.data = data; new_node.left = new_node.right = null; return new_node; } // A simple recursive function to convert // a given Binary tree to Doubly Linked List // root -. Root of Binary Tree // head_ref -. Pointer to head node of created // doubly linked list static void BToDLL(Node root) { // Base cases if (root == null) return; // Recursively convert right subtree BToDLL(root.right); // insert root into DLL root.right = head_ref; // Change left pointer of previous head if (head_ref != null) head_ref.left = root; // Change head of Doubly linked list head_ref = root; // Recursively convert left subtree BToDLL(root.left); } // Split a doubly linked list (DLL) // into 2 DLLs of half sizes static Node split(Node head) { Node fast = head, slow = head; while (fast.right != null && fast.right.right != null) { fast = fast.right.right; slow = slow.right; } Node temp = slow.right; slow.right = null; return temp; } // Function to merge two sorted // doubly linked lists static Node merge(Node first, Node second) { // If first linked list is empty if (first == null) return second; // If second linked list is empty if (second == null) return first; // Pick the smaller value if (first.data < second.data) { first.right = merge(first.right, second); first.right.left = first; first.left = null; return first; } else { second.right = merge(first, second.right); second.right.left = second; second.left = null; return second; } } // Function to do merge sort static Node mergeSort(Node head) { if (head == null || head.right == null) return head; Node second = split(head); // Recur for left and right halves head = mergeSort(head); second = mergeSort(second); // Merge the two sorted halves return merge(head, second); } // Function to count pairs in a sorted // doubly linked list whose sum equal // to given value x static int pairSum(Node head, int x) { // Set two pointers, first to the beginning // of DLL and second to the end of DLL. Node first = head; Node second = head; while (second.right != null) second = second.right; int count = 0; // The loop terminates when either of two pointers // become null, or they cross each other (second.right // == first), or they become same (first == second) while (first != null && second != null && first != second && second.right != first) { // pair found if ((first.data + second.data) == x) { count++; // move first in forward direction first = first.right; // move second in backward direction second = second.left; } else { if ((first.data + second.data) < x) first = first.right; else second = second.left; } } return count; } // function to count pairs in a binary tree // whose sum is equal to given value x static int countPairs(Node root, int x) { head_ref = null; // Convert binary tree to // doubly linked list BToDLL(root); // sort DLL head_ref = mergeSort(head_ref); // count pairs return pairSum(head_ref, x); } // Driver Code public static void main(String[] args) { // formation of binary tree Node root = getNode(5); /* 5 */ root.left = getNode(3); /* / \ */ root.right = getNode(7); /* 3 7 */ root.left.left = getNode(2); /* / \ / \ */ root.left.right = getNode(4); /* 2 4 6 8 */ root.right.left = getNode(6); root.right.right = getNode(8); int x = 10; System.out.print("Count = " + countPairs(root, x)); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to count pairs in a binary tree# whose sum is equal to given value x # structure of a node of a binary treeclass Node: def __init__(self, data): self.data = data self.left = None self.right = Nonehead_ref = None # function to create and return a node# of a binary treedef getNode(data): # allocate space for the node new_node = Node(data) return new_node # A simple recursive function to convert a given# Binary tree to Doubly Linked List# root -. Root of Binary Tree# head_ref -. Pointer to head node of created# doubly linked listdef BToDLL(root): global head_ref # Base cases if (root == None): return; # Recursively convert right subtree BToDLL(root.right) # insert root into DLL root.right = head_ref; # Change left pointer of previous head if (head_ref != None): (head_ref).left = root; # Change head of Doubly linked list head_ref = root; # Recursively convert left subtree BToDLL(root.left); return head_ref # Split a doubly linked list (DLL) into 2 DLLs of# half sizesdef split(head): fast = head slow = head; while (fast.right and fast.right.right): fast = fast.right.right; slow = slow.right; temp = slow.right; slow.right = None; return temp; # Function to merge two sorted doubly linked listsdef merge(first, second): # If first linked list is empty if (not first): return second; # If second linked list is empty if (not second): return first; # Pick the smaller value if (first.data < second.data): first.right = merge(first.right, second); first.right.left = first; first.left = None; return first; else: second.right = merge(first, second.right); second.right.left = second; second.left = None; return second; # Function to do merge sortdef mergeSort(head): if (head == None or head.right == None): return head; second = split(head); # Recur for left and right halves head = mergeSort(head); second = mergeSort(second); # Merge the two sorted halves return merge(head, second); # Function to count pairs in a sorted doubly linked list# whose sum equal to given value xdef pairSum(head, x): # Set two pointers, first to the beginning of DLL # and second to the end of DLL. first = head; second = head; while (second.right != None): second = second.right; count = 0; # The loop terminates when either of two pointers # become None, or they cross each other (second.right # == first), or they become same (first == second) while (first != None and second != None and first != second and second.right != first): # pair found if ((first.data + second.data) == x): count += 1 # move first in forward direction first = first.right; # move second in backward direction second = second.left; else: if ((first.data + second.data) < x): first = first.right; else: second = second.left; return count; # function to count pairs in a binary tree# whose sum is equal to given value xdef countPairs(root, x): global head_ref head_ref = None; # Convert binary tree to # doubly linked list BToDLL(root); # sort DLL head_ref = mergeSort(head_ref); # count pairs return pairSum(head_ref, x); # Driver codeif __name__=='__main__': # formation of binary tree root = getNode(5); # 5 root.left = getNode(3); # / \ root.right = getNode(7); # 3 7 root.left.left = getNode(2); # / \ / \ root.left.right = getNode(4);# 2 4 6 8 root.right.left = getNode(6); root.right.right = getNode(8); x = 10; print("Count = " + str(countPairs(root, x))) # This code is contributed by rutvik_56 |
C#
// C# implementation to count pairs // in a binary tree whose sum is // equal to the given value xusing System;class GFG { // structure of a node of a binary tree class Node { public int data; public Node left, right; }; static Node head_ref; // function to create and return a node // of a binary tree static Node getNode(int data) { // allocate space for the node Node new_node = new Node(); // put in the data new_node.data = data; new_node.left = new_node.right = null; return new_node; } // A simple recursive function to convert // a given Binary tree to Doubly Linked List // root -. Root of Binary Tree // head_ref -. Pointer to head node of // created doubly linked list static void BToDLL(Node root) { // Base cases if (root == null) return; // Recursively convert right subtree BToDLL(root.right); // insert root into DLL root.right = head_ref; // Change left pointer of previous head if (head_ref != null) head_ref.left = root; // Change head of Doubly linked list head_ref = root; // Recursively convert left subtree BToDLL(root.left); } // Split a doubly linked list (DLL) // into 2 DLLs of half sizes static Node split(Node head) { Node fast = head, slow = head; while (fast.right != null && fast.right.right != null) { fast = fast.right.right; slow = slow.right; } Node temp = slow.right; slow.right = null; return temp; } // Function to merge two sorted // doubly linked lists static Node merge(Node first, Node second) { // If first linked list is empty if (first == null) return second; // If second linked list is empty if (second == null) return first; // Pick the smaller value if (first.data < second.data) { first.right = merge(first.right, second); first.right.left = first; first.left = null; return first; } else { second.right = merge(first, second.right); second.right.left = second; second.left = null; return second; } } // Function to do merge sort static Node mergeSort(Node head) { if (head == null || head.right == null) return head; Node second = split(head); // Recur for left and right halves head = mergeSort(head); second = mergeSort(second); // Merge the two sorted halves return merge(head, second); } // Function to count pairs in a sorted // doubly linked list whose sum equal // to given value x static int pairSum(Node head, int x) { // Set two pointers, first to the beginning // of DLL and second to the end of DLL. Node first = head; Node second = head; while (second.right != null) second = second.right; int count = 0; // The loop terminates when either of // two pointers become null, or they // cross each other (second.right == first), // or they become same (first == second) while (first != null && second != null && first != second && second.right != first) { // pair found if ((first.data + second.data) == x) { count++; // move first in forward direction first = first.right; // move second in backward direction second = second.left; } else { if ((first.data + second.data) < x) first = first.right; else second = second.left; } } return count; } // function to count pairs in a binary tree // whose sum is equal to given value x static int countPairs(Node root, int x) { head_ref = null; // Convert binary tree to // doubly linked list BToDLL(root); // sort DLL head_ref = mergeSort(head_ref); // count pairs return pairSum(head_ref, x); } // Driver Code public static void Main(String[] args) { // formation of binary tree Node root = getNode(5); /* 5 */ root.left = getNode(3); /* / \ */ root.right = getNode(7); /* 3 7 */ root.left.left = getNode(2); /* / \ / \ */ root.left.right = getNode(4); /* 2 4 6 8 */ root.right.left = getNode(6); root.right.right = getNode(8); int x = 10; Console.Write("Count = " + countPairs(root, x)); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to count pairs // in a binary tree whose sum is // equal to the given value x // structure of a node of a binary tree class Node { constructor() { this.data = 0; this.left = null; this.right = null; } } var head_ref = null; // function to create and return a node // of a binary tree function getNode(data) { // allocate space for the node var new_node = new Node(); // put in the data new_node.data = data; new_node.left = new_node.right = null; return new_node; } // A simple recursive function to convert // a given Binary tree to Doubly Linked List // root -. Root of Binary Tree // head_ref -. Pointer to head node of // created doubly linked list function BToDLL(root) { // Base cases if (root == null) return; // Recursively convert right subtree BToDLL(root.right); // insert root into DLL root.right = head_ref; // Change left pointer of previous head if (head_ref != null) head_ref.left = root; // Change head of Doubly linked list head_ref = root; // Recursively convert left subtree BToDLL(root.left); } // Split a doubly linked list (DLL) // into 2 DLLs of half sizes function split(head) { var fast = head, slow = head; while (fast.right != null && fast.right.right != null) { fast = fast.right.right; slow = slow.right; } var temp = slow.right; slow.right = null; return temp; } // Function to merge two sorted // doubly linked lists function merge(first, second) { // If first linked list is empty if (first == null) return second; // If second linked list is empty if (second == null) return first; // Pick the smaller value if (first.data < second.data) { first.right = merge(first.right, second); first.right.left = first; first.left = null; return first; } else { second.right = merge(first, second.right); second.right.left = second; second.left = null; return second; } } // Function to do merge sort function mergeSort(head) { if (head == null || head.right == null) return head; var second = split(head); // Recur for left and right halves head = mergeSort(head); second = mergeSort(second); // Merge the two sorted halves return merge(head, second); } // Function to count pairs in a sorted // doubly linked list whose sum equal // to given value x function pairSum(head, x) { // Set two pointers, first to the beginning // of DLL and second to the end of DLL. var first = head; var second = head; while (second.right != null) second = second.right; var count = 0; // The loop terminates when either of // two pointers become null, or they // cross each other (second.right == first), // or they become same (first == second) while ( first != null && second != null && first != second && second.right != first ) { // pair found if (first.data + second.data == x) { count++; // move first in forward direction first = first.right; // move second in backward direction second = second.left; } else { if (first.data + second.data < x) first = first.right; else second = second.left; } } return count; } // function to count pairs in a binary tree // whose sum is equal to given value x function countPairs(root, x) { head_ref = null; // Convert binary tree to // doubly linked list BToDLL(root); // sort DLL head_ref = mergeSort(head_ref); // count pairs return pairSum(head_ref, x); } // Driver Code // formation of binary tree var root = getNode(5); /* 5 */ root.left = getNode(3); /* / \ */ root.right = getNode(7); /* 3 7 */ root.left.left = getNode(2); /* / \ / \ */ root.left.right = getNode(4); /* 2 4 6 8 */ root.right.left = getNode(6); root.right.right = getNode(8); var x = 10; document.write("Count = " + countPairs(root, x)); </script> |
Output
Count = 3
Time Complexity: O(nLog n).
Auxiliary Space: O(N)
3)Another Efficient Approach – No need for converting to DLL and sorting: Following are the steps:
- Traverse the tree in any order (pre / post / in).
- Create an empty hash and keep adding difference between current node’s value and X to it.
- At each node, check if it’s value is in the hash, if yes then increment the count by 1 and DO NOT add this node’s value’s difference with X in the hash to avoid duplicate counting for a single pair.
Implementation:
C++
#include <iostream>#include <unordered_set>using namespace std;// Node class to represent a// node in the binary tree// with value, left and right attributesclass Node {public: int value; Node* left; Node* right; Node(int value, Node* left = nullptr, Node* right = nullptr) : value(value), left(left), right(right) {}};// To store count of pairsint count = 0;// To store difference between// current node's value and x,// acts a lookup for counting pairsunordered_set<int> hash_t;// The input, we need to count// pairs whose sum is equal to xint x = 10;// Function to count number of pairs// Does a pre-order traversal of the treevoid count_pairs_w_sum(Node* root) { if (root != nullptr) { if (hash_t.count(root->value)) { count++; } else { hash_t.insert(x - root->value); } count_pairs_w_sum(root->left); count_pairs_w_sum(root->right); }}// Entry point / Driver - Create a// binary tree and call the function// to get the countint main() { Node* root = new Node(5); root->left = new Node(3); root->right = new Node(7); root->left->left = new Node(2); root->left->right = new Node(4); root->right->left = new Node(6); root->right->right = new Node(8); count_pairs_w_sum(root); cout << count << endl; return 0;}// This code is contributed by lokeshpotta20. |
Java
// Java program to Count pairs// in a binary tree whose sum is// equal to a given value ximport java.util.HashSet;public class GFG{ // Node class to represent a // node in the binary tree // with value, left and right attributes static class Node { int value; Node left, right; public Node(int value) { this.value = value; } } // To store count of pairs static int count = 0; // To store difference between // current node's value and x, // acts a lookup for counting pairs static HashSet<Integer> hash_t = new HashSet<Integer>(); // The input, we need to count // pairs whose sum is equal to x static int x = 10; // Function to count number of pairs // Does a pre-order traversal of the tree static void count_pairs_w_sum(Node root) { if( root != null) { if (hash_t.contains(root.value)) count += 1; else hash_t.add(x-root.value); count_pairs_w_sum(root.left); count_pairs_w_sum(root.right); } } //Driver method public static void main(String[] args) { Node root = new Node(5); root.left = new Node(3); root.right = new Node(7); root.left.left = new Node(2); root.left.right = new Node(4); root.right.left = new Node(6); root.right.right = new Node(8); count_pairs_w_sum(root); System.out.println(count); }}// This code is contributed by Lovely Jain |
Python
# Python program to Count pairs# in a binary tree whose sum is# equal to a given value x# Node class to represent a# node in the binary tree# with value, left and right attributesclass Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right# To store count of pairscount = 0# To store difference between# current node's value and x,# acts a lookup for counting pairshash_t = set()# The input, we need to count# pairs whose sum is equal to xx = 10# Function to count number of pairs# Does a pre-order traversal of the treedef count_pairs_w_sum(root): global count if root: if root.value in hash_t: count += 1 else: hash_t.add(x-root.value) count_pairs_w_sum(root.left) count_pairs_w_sum(root.right)# Entry point / Driver - Create a# binary tree and call the function# to get the countif __name__ == '__main__': root = Node(5) root.left = Node(3) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(4) root.right.left = Node(6) root.right.right = Node(8) count_pairs_w_sum(root) print count |
C#
// C# program to count pairs in binary tree whose sum is// equal to a given value in xusing System;using System.Collections.Generic;public class GFG { // Node class to represent a // node in the binary tree // with value, left and right attributes class Node { public int value; public Node left, right; public Node(int value) { this.value = value; } } // To stsore count of pairs static int count = 0; // To store difference between // current node's value and x, // acts a lookup for counting pairs static HashSet<int> hash_t = new HashSet<int>(); // The input, we need to count // pairs whose sum is equal to x static int x = 10; // Function to count number of pairs // Does a pre-order traversal of the tree static void count_pairs_w_sum(Node root) { if (root != null) { if (hash_t.Contains(root.value)) count += 1; else hash_t.Add(x - root.value); count_pairs_w_sum(root.left); count_pairs_w_sum(root.right); } } static public void Main() { // Code Node root = new Node(5); root.left = new Node(3); root.right = new Node(7); root.left.left = new Node(2); root.left.right = new Node(4); root.right.left = new Node(6); root.right.right = new Node(8); count_pairs_w_sum(root); Console.WriteLine(count); }}// This code is contributed by lokeshmvs21. |
Javascript
// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL// JavaScript program to count pairs in binary tree whose sum is// equal to a given value in xclass Node{ constructor(value){ this.value = value; this.left = null; this.right = null; }}// To store count of pairslet count = 0;// To store difference between// current node's value and x,// acts a lookup for counting pairslet hash_t = new Set();// The input, we need to count// pairs whose sum is equal to xlet x = 10;// Function to count number of pairs// Does a pre-order traversal of the treefunction count_pairs_w_sum(root){ if(root != null){ if(hash_t.has(root.value)){ count++; } else{ hash_t.add(x-root.value); } count_pairs_w_sum(root.left); count_pairs_w_sum(root.right); }}// Entry point / Driver - Create a// binary tree and call the function// to get the countlet root = new Node(5);root.left = new Node(3);root.right = new Node(7);root.left.left = new Node(2);root.left.right = new Node(4);root.right.left = new Node(6);root.right.right = new Node(8);count_pairs_w_sum(root);console.log(count); |
Output
3
Complexity Analysis:
- Time Complexity: O(n)
- Space Complexity: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
