Posted on by Kalkicode
Code Binary Search Tree

Find all pair with given sum in BST

Here given code implementation process.

``````//C Program
//Find all pair with given sum in BST
#include <stdio.h>

#include <stdlib.h>
//structure of Binary Search Tree node
struct Node {
int data;
struct Node *left, *right;
};

//Adding a new node in binary search tree
void add(struct Node **root, int data) {
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));

if (new_node != NULL) {
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL

if ( *root == NULL) {
//When adds a first node in binary tree
*root = new_node;
} else {
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while (find != NULL) {
if (find->data > data) {
if (find->left == NULL) {
find->left = new_node;
break;
} else { //visit left sub-tree
find = find->left;
}
} else {
if (find->right == NULL) {
find->right = new_node;
break;
} else {
//visit right sub-tree
find = find->right;
}
}
}
}
} else {
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}

}

int counter(struct Node *root) {
if (root != NULL) {

return counter(root->left) + counter(root->right) + 1;

}
return 0;
}
void get_elements(struct Node *root, int *auxiliary, int *index) {
if (root != NULL) {

get_elements(root->left, auxiliary, index);
auxiliary[ *index] += root->data;
( *index) ++;
get_elements(root->right, auxiliary, index);

}
}
void pair_sum(struct Node *root, int sum) {
if (root != NULL) {

int size = counter(root);

int *auxiliary = (int *) calloc(size, sizeof(int));

int index = 0;
get_elements(root, auxiliary, & index);

index = 0;
size--;
int status = 0;
while (index < size) {
if (auxiliary[index] + auxiliary[size] == sum) {
status = 1;
break;
} else if (auxiliary[index] + auxiliary[size] > sum) {
size--;
} else {
index++;
}
}
if (status != 1) {
printf("\nPair of Sum %d are not exist \n", sum);
} else {

printf("\n Pair of Sum : %d\n", sum);
while (index <= size) {
for (int i = index + 1; i <= size; ++i) {

if (auxiliary[index] + auxiliary[i] == sum) {
printf("(%d,%d) ", auxiliary[index], auxiliary[i]);
}
}
index++;
}
}

free(auxiliary);

auxiliary = NULL;

}
printf("\n");

}

int main() {

struct Node *root = NULL;

//Add nodes in binary search tree
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7       12

*/

pair_sum(root, 16);
pair_sum(root, 6);
return 0;
}```
```

Output

`````` Pair of Sum : 16
(4,12) (5,11) (7,9)

Pair of Sum : 6
(-3,9) (1,5) (2,4)
``````
``````/*
C++ Program
Convert a binary tree to Max Heap
*/
#include<iostream>

using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree {
public:
Node *root;
int counter;
BinarySearchTree() {
this->root = NULL;
this->counter = 0;
}
Node *new_node = new Node(value);
if (new_node != NULL) {
if (this->root == NULL) {
this->root = new_node;
} else {
Node *find = this->root;
while (find != NULL) {
if (find->data >= value) {
if (find->left == NULL) {
find->left = new_node;
break;;
} else {
find = find->left;
}
} else {
if (find->right == NULL) {
find->right = new_node;
break;;
} else {
find = find->right;
}
}
}
}
} else {
cout << ("\nMemory Overflow\n");
}
}
}
return 0;
}
void get_elements(Node *head, int *auxiliary) {
this->counter++;
}
}
void pair_sum(int sum) {
if (this->root != NULL) {
int size = this->counter_nodes(this->root);
int *auxiliary = new int[size];
int i = 0, index = 0;
bool status = false;
this->counter = 0;
this->get_elements(this->root, auxiliary);
size--;
while (index < size) {
if (auxiliary[index] + auxiliary[size] == sum) {
status = true;
break;
} else
if (auxiliary[index] + auxiliary[size] > sum) {
size--;
} else {
index++;
}
}
if (status == false) {
cout << "\nPair of Sum " << sum << " are not exist \n";
} else {
cout << "\n Pair of Sum : " << sum << "\n";
while (index <= size) {
i = index + 1;
while (i <= size) {
if (auxiliary[index] + auxiliary[i] == sum) {
cout << "  (" << auxiliary[index] << "," << auxiliary[i] << ")";
}
i++;
}
index++;
}
}
}
}
};
int main() {
BinarySearchTree obj;
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7       12

*/
obj.pair_sum(16);
obj.pair_sum(6);
return 0;
}```
```

Output

`````` Pair of Sum : 16
(4,12) (5,11) (7,9)

Pair of Sum : 6
(-3,9) (1,5) (2,4)
``````
``````//Java program
//Find all pair with given sum in BST
class Node {
public int data;
public Node left;
public Node right;

public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {

public Node root;

public int counter;

BinarySearchTree() {
root = null;
counter = 0;
}
//insert a node in BST
//Create a dynamic node of binary search tree
Node new_node = new Node(value);

if (new_node != null) {
if (root == null) {
//When adds a first node in binary tree
root = new_node;
} else {
Node find = root;

//add new node to proper position
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
//visit left sub-tree
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
//visit right sub-tree
find = find.right;
}
}
}
}
} else {
System.out.print("\nMemory Overflow\n");
}
}

}
return 0;
}
public void get_elements(Node head, int[] auxiliary) {

this.counter++;
}
}
public void pair_sum(int sum) {
if (root != null) {

int size = counter_nodes(root);

int[] auxiliary = new int[size];

int i = 0, index = 0;

boolean status = false;

this.counter = 0;

get_elements(root, auxiliary);

size--;
//Check given sum pair are exist or not
while (index < size) {
if (auxiliary[index] + auxiliary[size] == sum) {
status = true;
break;
} else if (auxiliary[index] + auxiliary[size] > sum) {
size--;
} else {
index++;
}
}
if (status == false) {
System.out.print("\nPair of Sum " + sum + " are not exist \n");
} else {

System.out.print("\n Pair of Sum : " + sum + "\n");

while (index <= size) {

i = index + 1;

while (i <= size) {

if (auxiliary[index] + auxiliary[i] == sum) {
System.out.print("  (" + auxiliary[index] + "," + auxiliary[i] + ")");
}
i++;
}

index++;
}
}
}

}
public static void main(String[] args) {

BinarySearchTree obj = new BinarySearchTree();

//Add nodes in binary search tree
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7        12

*/

obj.pair_sum(16);
obj.pair_sum(6);
}
}```
```

Output

`````` Pair of Sum : 16
(4,12) (5,11) (7,9)

Pair of Sum : 6
(-3,9) (1,5) (2,4)
``````
``````//C# program
//Find all pair with given sum in BST
using System;
public class Node {
public int data;
public Node left;
public Node right;

public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {

public Node root;

public int counter;

BinarySearchTree() {
root = null;
counter = 0;
}
//insert a node in BST
//Create a dynamic node of binary search tree
Node new_node = new Node(value);

if (new_node != null) {
if (root == null) {
//When adds a first node in binary tree
root = new_node;
} else {
Node find = root;

//add new node to proper position
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
//visit left sub-tree
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
//visit right sub-tree
find = find.right;
}
}
}
}
} else {
Console.Write("\nMemory Overflow\n");
}
}

}
return 0;
}
public void get_elements(Node head, int[] auxiliary) {

this.counter++;
}
}
public void pair_sum(int sum) {
if (root != null) {

int size = counter_nodes(root);

int[] auxiliary = new int[size];

int i = 0, index = 0;

Boolean status = false;

this.counter = 0;

get_elements(root, auxiliary);

size--;
//Check given sum pair are exist or not
while (index < size) {
if (auxiliary[index] + auxiliary[size] == sum) {
status = true;
break;
} else if (auxiliary[index] + auxiliary[size] > sum) {
size--;
} else {
index++;
}
}
if (status == false) {
Console.Write("\nPair of Sum " + sum + " are not exist \n");
} else {

Console.Write("\n Pair of Sum : " + sum + "\n");

while (index <= size) {

i = index + 1;

while (i <= size) {

if (auxiliary[index] + auxiliary[i] == sum) {
Console.Write("  (" + auxiliary[index] + "," + auxiliary[i] + ")");
}
i++;
}

index++;
}
}
}

}
public static void Main(String[] args) {

BinarySearchTree obj = new BinarySearchTree();

//Add nodes in binary search tree
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7        12

*/

obj.pair_sum(16);
obj.pair_sum(6);
}
}```
```

Output

`````` Pair of Sum : 16
(4,12) (5,11) (7,9)

Pair of Sum : 6
(-3,9) (1,5) (2,4)
``````
``````# Python Program
# Find all pair with given sum in BST
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None

class BinarySearchTree :

def __init__(self) :
self.root = None
self.counter = 0

new_node = Node(value)
if (new_node != None) :
if (self.root == None) :
self.root = new_node
else :
find = self.root
while (find != None) :
if (find.data >= value) :
if (find.left == None) :
find.left = new_node
break
else :
find = find.left

else :
if (find.right == None) :
find.right = new_node
break
else :
find = find.right

else :
print("\nMemory Overflow\n")

return 0

self.counter += 1

def pair_sum(self, given_sum) :
if (self.root != None) :
size = self.counter_nodes(self.root)
auxiliary = [0]*size
i = 0
index = 0
status = False
self.counter = 0
self.get_elements(self.root, auxiliary)
size -= 1
while (index < size) :
if (auxiliary[index] + auxiliary[size] == given_sum) :
status = True
break
elif (auxiliary[index] + auxiliary[size] > given_sum) :
size -= 1
else :
index += 1

if (status == False) :
print("\nPair of Sum ", given_sum ," are not exist ")
else :
print("\n Pair of Sum : ", given_sum )

while (index <= size) :
i = index + 1
while (i <= size) :
if (auxiliary[index] + auxiliary[i] == given_sum) :
print("(", auxiliary[index] ,",", auxiliary[i] ,")",end=" ")

i += 1

index += 1

def main() :
obj = BinarySearchTree()
#
#             5
#           /    \
#          3      9
#         / \     / \
#        1   4   8   11
#       / \     /      \
#      -3  2    7       12
#
obj.pair_sum(16)
obj.pair_sum(6)

if __name__ == "__main__":
main()```
```

Output

`````` Pair of Sum :  16
( 4 , 12 ) ( 5 , 11 ) ( 7 , 9 )
Pair of Sum :  6
( -3 , 9 ) ( 1 , 5 ) ( 2 , 4 )``````
``````# Ruby Program
# Find all pair with given sum in BST
class Node
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end

class BinarySearchTree
attr_accessor :root, :counter
def initialize()
@root = nil
@counter = 0
end
new_node = Node.new(value)
if (new_node != nil)
if (@root == nil)
@root = new_node
else
find = @root
while (find != nil)
if (find.data >= value)
if (find.left == nil)
find.left = new_node
break
else
find = find.left
end
else
if (find.right == nil)
find.right = new_node
break
else
find = find.right
end
end
end
end
else
print("\nMemory Overflow\n")
end
end
end
return 0
end
self.counter += 1
end
end
def pair_sum(sum)
if (@root != nil)
size = self.counter_nodes(@root)
auxiliary = Array.new(size,0)
i = 0
index = 0
status = false
self.counter = 0
self.get_elements(@root, auxiliary)
size -= 1
while (index < size)
if (auxiliary[index] + auxiliary[size] == sum)
status = true
break
elsif (auxiliary[index] + auxiliary[size] > sum)
size -= 1
else
index += 1
end
end
if (status == false)
print("\nPair of Sum ", sum ," are not exist \n")
else
print("\n Pair of Sum  :", sum ,"\n")
while (index <= size)
i = index + 1
while (i <= size)
if (auxiliary[index] + auxiliary[i] == sum)
print("  (", auxiliary[index] ,",", auxiliary[i] ,")")
end
i += 1
end
index += 1
end
end
end
end

end
def main()
obj = BinarySearchTree.new()
#
#             5
#           /    \
#          3      9
#         / \     / \
#        1   4   8   11
#       / \     /      \
#      -3  2    7       12
#
obj.pair_sum(16)
obj.pair_sum(6)
end

main()```
```

Output

`````` Pair of Sum  :16
(4,12)  (5,11)  (7,9)
Pair of Sum  :6
(-3,9)  (1,5)  (2,4)``````
``````<?php
/*
Php Program
Find all pair with given sum in BST
*/
class Node {
public \$data;
public \$left;
public \$right;

function __construct(\$value) {
\$this->data = \$value;
\$this->left = null;
\$this->right = null;
}
}
class BinarySearchTree {
public \$root;
public \$counter;

function __construct() {
\$this->root = null;
\$this->counter = 0;
}
\$new_node = new Node(\$value);
if (\$new_node != null) {
if (\$this->root == null) {
\$this->root = \$new_node;
} else {
\$find = \$this->root;
while (\$find != null) {
if (\$find->data >= \$value) {
if (\$find->left == null) {
\$find->left = \$new_node;
break;;
} else {
\$find = \$find->left;
}
} else {
if (\$find->right == null) {
\$find->right = \$new_node;
break;;
} else {
\$find = \$find->right;
}
}
}
}
} else {
echo("\nMemory Overflow\n");
}
}

}
return 0;
}
\$this->counter++;
}
}
public  function pair_sum(\$sum) {
if (\$this->root != null) {
\$size = \$this->counter_nodes(\$this->root);
\$auxiliary = array_fill(0, \$size, 0);
\$i = 0;
\$index = 0;
\$status = false;
\$this->counter = 0;
\$this->get_elements(\$this->root, \$auxiliary);
\$size--;
while (\$index < \$size) {
if (\$auxiliary[\$index] + \$auxiliary[\$size] == \$sum) {
\$status = true;
break;
} else
if (\$auxiliary[\$index] + \$auxiliary[\$size] > \$sum) {
\$size--;
} else {
\$index++;
}
}
if (\$status == false) {
echo("\nPair of Sum ". \$sum ." are not exist \n");
} else {
echo("\n Pair of Sum : ". \$sum ."\n");
while (\$index <= \$size) {
\$i = \$index + 1;
while (\$i <= \$size) {
if (\$auxiliary[\$index] + \$auxiliary[\$i] == \$sum) {
echo("  (". \$auxiliary[\$index] .",". \$auxiliary[\$i] .")");
}
\$i++;
}
\$index++;
}
}
}
}
}
function main() {
\$obj = new BinarySearchTree();
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7       12

*/
\$obj->pair_sum(16);
\$obj->pair_sum(6);
}
main();```
```

Output

`````` Pair of Sum  :16
(4,12)  (5,11)  (7,9)
Pair of Sum  :6
(-3,9)  (1,5)  (2,4)``````
``````/*
Node JS Program
Find all pair with given sum in BST
*/
class Node {

constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {

constructor() {
this.root = null;
this.counter = 0;
}
var new_node = new Node(value);
if (new_node != null) {
if (this.root == null) {
this.root = new_node;
} else {
var find = this.root;
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;;
} else {
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;;
} else {
find = find.right;
}
}
}
}
} else {
process.stdout.write("\nMemory Overflow\n");
}
}
}
return 0;
}
this.counter++;
}
}
pair_sum(sum) {
if (this.root != null) {
var size = this.counter_nodes(this.root);
var auxiliary = Array(size).fill(0);;
var i = 0;
var index = 0;
var status = false;
this.counter = 0;
this.get_elements(this.root, auxiliary);
size--;
while (index < size) {
if (auxiliary[index] + auxiliary[size] == sum) {
status = true;
break;;
} else
if (auxiliary[index] + auxiliary[size] > sum) {
size--;
} else {
index++;
}
}
if (status == false) {
process.stdout.write("\nPair of Sum " + sum + " are not exist \n");
} else {
process.stdout.write("\n Pair of Sum : " + sum + "\n");
while (index <= size) {
i = index + 1;
while (i <= size) {
if (auxiliary[index] + auxiliary[i] == sum) {
process.stdout.write("  (" + auxiliary[index] + "," + auxiliary[i] + ")");
}
i++;
}
index++;
}
}
}
}
}
function main() {
var obj = new BinarySearchTree();
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7       12

*/
obj.pair_sum(16);
obj.pair_sum(6);
}
main();```
```

Output

`````` Pair of Sum  :16
(4,12)  (5,11)  (7,9)
Pair of Sum  :6
(-3,9)  (1,5)  (2,4)``````
``````/*
Swift 4 Program
Find all pair with given sum in BST
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree {
var root: Node? ;
var counter: Int;
init() {
self.root = nil;
self.counter = 0;
}
let new_node: Node? = Node(value);
if (new_node != nil) {
if (self.root == nil) {
self.root = new_node;
} else {
var find: Node? = self.root;
while (find != nil) {
if (find!.data >= value) {
if (find!.left == nil) {
find!.left = new_node;
break;
} else {
find = find!.left;
}
} else {
if (find!.right == nil) {
find!.right = new_node;
break;
} else {
find = find!.right;
}
}
}
}
} else {
print("\nMemory Overflow\n");
}
}
func counter_nodes(_ head: Node? ) -> Int {
}
return 0;
}
func get_elements(_ head: Node? , _ auxiliary : inout [Int]) {
self.counter += 1;
}
}
func pair_sum(_ sum: Int) {
if (self.root != nil) {
var size: Int = self.counter_nodes(self.root);
var auxiliary: [Int] = Array(repeating:0,count:size);
var i: Int = 0;
var index = 0;
var status: Bool = false;
self.counter = 0;
self.get_elements(self.root, &auxiliary);
size -= 1;
while (index < size) {
if (auxiliary[index] + auxiliary[size] == sum) {
status = true;
break;
} else
if (auxiliary[index] + auxiliary[size] > sum) {
size -= 1;
} else {
index += 1;
}
}
if (status == false) {
print("\nPair of Sum ", sum ," are not exist \n");
} else {
print("\n Pair of Sum : ", sum ,"\n");
while (index <= size) {
i = index + 1;
while (i <= size) {
if (auxiliary[index] + auxiliary[i] == sum) {
print("  (", auxiliary[index] ,",", auxiliary[i] ,")");
}
i += 1;
}
index += 1;
}
}
}
}
}
func main() {
let obj: BinarySearchTree = BinarySearchTree();
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2    7       12
*/
obj.pair_sum(16);
obj.pair_sum(6);
}
main();```
```

Output

`````` Pair of Sum :  16

( 4 , 12 )
( 5 , 11 )
( 7 , 9 )

Pair of Sum :  6

( -3 , 9 )
( 1 , 5 )
( 2 , 4 )
``````

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post