Sum of cousin nodes of a given node in a BST
Here given code implementation process.
/*
C Program
Sum of cousin nodes of a given node in a BST
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Search Tree
struct BinarySearchTree
{
struct TreeNode *root;
};
// Create new tree
struct BinarySearchTree *newTree()
{
// Create dynamic node
struct BinarySearchTree *tree =
(struct BinarySearchTree *) malloc(sizeof(struct BinarySearchTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// Return new tree
return tree;
}
// Returns a new node of tree
struct TreeNode *newTreeNode(int data)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
// Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
// Return new node
return node;
}
// Adding a new node in binary search tree
void addNode(struct BinarySearchTree *tree, int data)
{
struct TreeNode *node = newTreeNode(data);
if (node != NULL)
{
if (tree->root == NULL)
{
tree->root = node;
}
else
{
struct TreeNode *auxiliary = tree->root;
// Add new node in binary search tree
while (auxiliary != NULL)
{
if (data > auxiliary->data)
{
if (auxiliary->right == NULL)
{
// Add new node at right child
auxiliary->right = node;
return;
}
auxiliary = auxiliary->right;
}
else
{
if (auxiliary->left == NULL)
{
// Add new node at left child
auxiliary->left = node;
return;
}
auxiliary = auxiliary->left;
}
}
}
}
}
struct TreeNode *findParent(int value,
struct TreeNode *node,
int count,
int *level)
{
if (node != NULL)
{
if ((node->left != NULL && node->left->data == value) ||
(node->right != NULL && node->right->data == value))
{
// Find level of node
*level = count + 1;
// Returns the parent of the data
return node;
}
struct TreeNode *p = NULL;
// Find node value in left subtree
p = findParent(value, node->left, count + 1, level);
if (p == NULL)
{
// When need to find node value in right subtree
p = findParent(value, node->right, count + 1, level);
}
return p;
}
return NULL;
}
int cousinSum(struct TreeNode *node,
struct TreeNode *parent, int level, int position)
{
if (node != NULL && node != parent && position <= level)
{
if (position == level)
{
return node->data;
}
// Sum of cousin node
return cousinSum(node->left, parent, level, position + 1) +
cousinSum(node->right, parent, level, position + 1);
}
return 0;
}
void findCousinSum(struct TreeNode *root, int node)
{
printf("\n Given node value : %d\n", node);
if (root->data == node)
{
printf("Result : 0\n");
return;
}
int level = -1;
struct TreeNode *p = findParent(node, root, 0, & level);
if (p == NULL)
{
// Given node not present
printf(" Result : node not exists\n");
}
else
{
int sum = cousinSum(root, p, level, 0);
// Display cousin sum
printf(" Result : %d\n", sum);
}
}
int main()
{
struct BinarySearchTree *tree = newTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
addNode(tree, 15);
addNode(tree, 13);
addNode(tree, 12);
addNode(tree, 14);
addNode(tree, 11);
addNode(tree, 20);
addNode(tree, 18);
addNode(tree, 19);
addNode(tree, 21);
addNode(tree, 22);
addNode(tree, 16);
addNode(tree, 17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
findCousinSum(tree->root, 14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
findCousinSum(tree->root, 22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
findCousinSum(tree->root, 17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
findCousinSum(tree->root, 13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
findCousinSum(tree->root, 21);
findCousinSum(tree->root, 8);
return 0;
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
/*
Java program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree
{
public TreeNode root;
public int level;
public BinarySearchTree()
{
this.root = null;
this.level = 0;
}
public void addNode(int data)
{
// Create a new node
TreeNode node = new TreeNode(data);
if (this.root == null)
{
// When add a first node
this.root = node;
}
else
{
// Get root of tree
TreeNode find = this.root;
// Find position to insert new node
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
public TreeNode findParent(int value, TreeNode node, int count)
{
if (node != null)
{
if ((node.left != null && node.left.data == value) || (node.right != null && node.right.data == value))
{
// Find level of node
this.level = count + 1;
// Returns the parent of the data
return node;
}
TreeNode p = null;
// Find node value in left subtree
p = findParent(value, node.left, count + 1);
if (p == null)
{
// When need to find node value in right subtree
p = findParent(value, node.right, count + 1);
}
return p;
}
return null;
}
public int cousinSum(TreeNode node, TreeNode parent, int position)
{
if (node != null && node != parent && position <= this.level)
{
if (position == this.level)
{
return node.data;
}
// Sum of cousin node
return cousinSum(node.left, parent, position + 1) + cousinSum(node.right, parent, position + 1);
}
return 0;
}
public void findCousinSum(int node)
{
System.out.println("\n Given node value : " + node);
if (this.root == null)
{
System.out.println("\n Empty Tree ");
return;
}
if (this.root.data == node)
{
System.out.print("Result : 0\n");
return;
}
this.level = -1;
TreeNode p = findParent(node, root, 0);
if (p == null)
{
// Given node not present
System.out.println(" Result : node not exists");
}
else
{
int sum = cousinSum(this.root, p, 0);
// Display cousin sum
System.out.println(" Result : " + sum);
}
}
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15);
tree.addNode(13);
tree.addNode(12);
tree.addNode(14);
tree.addNode(11);
tree.addNode(20);
tree.addNode(18);
tree.addNode(19);
tree.addNode(21);
tree.addNode(22);
tree.addNode(16);
tree.addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21);
tree.findCousinSum(8);
}
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree
{
public: TreeNode *root;
int level;
BinarySearchTree()
{
this->root = NULL;
this->level = 0;
}
void addNode(int data)
{
// Create a new node
TreeNode *node = new TreeNode(data);
if (this->root == NULL)
{
// When add a first node
this->root = node;
}
else
{
// Get root of tree
TreeNode *find = this->root;
// Find position to insert new node
while (find != NULL)
{
if (find->data >= data)
{
if (find->left == NULL)
{
find->left = node;
return;
}
else
{
// Visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = node;
return;
}
else
{
// Visit right sub-tree
find = find->right;
}
}
}
}
}
TreeNode *findParent(int value, TreeNode *node, int count)
{
if (node != NULL)
{
if ((node->left != NULL && node->left->data == value) ||
(node->right != NULL && node->right->data == value))
{
// Find level of node
this->level = count + 1;
// Returns the parent of the data
return node;
}
TreeNode *p = NULL;
// Find node value in left subtree
p = this->findParent(value, node->left, count + 1);
if (p == NULL)
{
// When need to find node value in right subtree
p = this->findParent(value, node->right, count + 1);
}
return p;
}
return NULL;
}
int cousinSum(TreeNode *node, TreeNode *parent, int position)
{
if (node != NULL && node != parent && position <= this->level)
{
if (position == this->level)
{
return node->data;
}
// Sum of cousin node
return this->cousinSum(node->left, parent, position + 1) +
this->cousinSum(node->right, parent, position + 1);
}
return 0;
}
void findCousinSum(int node)
{
cout << "\n Given node value : " << node << endl;
if (this->root == NULL)
{
cout << "\n Empty Tree " << endl;
return;
}
if (this->root->data == node)
{
cout << "Result : 0\n";
return;
}
this->level = -1;
TreeNode *p = this->findParent(node, this->root, 0);
if (p == NULL)
{
// Given node not present
cout << " Result : node not exists" << endl;
}
else
{
int sum = this->cousinSum(this->root, p, 0);
// Display cousin sum
cout << " Result : " << sum << endl;
}
}
};
int main()
{
BinarySearchTree *tree = new BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree->addNode(15);
tree->addNode(13);
tree->addNode(12);
tree->addNode(14);
tree->addNode(11);
tree->addNode(20);
tree->addNode(18);
tree->addNode(19);
tree->addNode(21);
tree->addNode(22);
tree->addNode(16);
tree->addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree->findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree->findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree->findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree->findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree->findCousinSum(21);
tree->findCousinSum(8);
return 0;
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
package main
import "fmt"
/*
Go program
Sum of cousin nodes of a given node in a BST
*/
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
return me
}
type BinarySearchTree struct {
root * TreeNode
level int
}
func getBinarySearchTree() * BinarySearchTree {
var me *BinarySearchTree = &BinarySearchTree {}
me.root = nil
me.level = 0
return me
}
func(this *BinarySearchTree) addNode(data int) {
// Create a new node
var node * TreeNode = getTreeNode(data)
if this.root == nil {
// When add a first node
this.root = node
} else {
// Get root of tree
var find * TreeNode = this.root
// Find position to insert new node
for (find != nil) {
if find.data >= data {
if find.left == nil {
find.left = node
return
} else {
// Visit left sub-tree
find = find.left
}
} else {
if find.right == nil {
find.right = node
return
} else {
// Visit right sub-tree
find = find.right
}
}
}
}
}
func(this *BinarySearchTree) findParent(value int,
node * TreeNode, count int) * TreeNode {
if node != nil {
if (node.left != nil && node.left.data == value) ||
(node.right != nil && node.right.data == value) {
// Find level of node
this.level = count + 1
// Returns the parent of the data
return node
}
var p * TreeNode = nil
// Find node value in left subtree
p = this.findParent(value, node.left, count + 1)
if p == nil {
// When need to find node value in right subtree
p = this.findParent(value, node.right, count + 1)
}
return p
}
return nil
}
func(this BinarySearchTree) cousinSum(node * TreeNode,
parent * TreeNode, position int) int {
if node != nil && node != parent && position <= this.level {
if position == this.level {
return node.data
}
// Sum of cousin node
return this.cousinSum(node.left, parent, position + 1) +
this.cousinSum(node.right, parent, position + 1)
}
return 0
}
func(this BinarySearchTree) findCousinSum(node int) {
fmt.Println("\n Given node value : ", node)
if this.root == nil {
fmt.Println("\n Empty Tree ")
return
}
if this.root.data == node {
fmt.Print("Result : 0\n")
return
}
this.level = -1
var p * TreeNode = this.findParent(node, this.root, 0)
if p == nil {
// Given node not present
fmt.Println(" Result : node not exists")
} else {
var sum int = this.cousinSum(this.root, p, 0)
// Display cousin sum
fmt.Println(" Result : ", sum)
}
}
func main() {
var tree * BinarySearchTree = getBinarySearchTree()
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15)
tree.addNode(13)
tree.addNode(12)
tree.addNode(14)
tree.addNode(11)
tree.addNode(20)
tree.addNode(18)
tree.addNode(19)
tree.addNode(21)
tree.addNode(22)
tree.addNode(16)
tree.addNode(17)
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14)
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22)
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17)
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13)
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21)
tree.findCousinSum(8)
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
// Include namespace system
using System;
/*
Csharp program
Sum of cousin nodes of a given node in a BST
*/
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree
{
public TreeNode root;
public int level;
public BinarySearchTree()
{
this.root = null;
this.level = 0;
}
public void addNode(int data)
{
// Create a new node
TreeNode node = new TreeNode(data);
if (this.root == null)
{
// When add a first node
this.root = node;
}
else
{
// Get root of tree
TreeNode find = this.root;
// Find position to insert new node
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
public TreeNode findParent(int value, TreeNode node, int count)
{
if (node != null)
{
if ((node.left != null && node.left.data == value) ||
(node.right != null && node.right.data == value))
{
// Find level of node
this.level = count + 1;
// Returns the parent of the data
return node;
}
TreeNode p = null;
// Find node value in left subtree
p = this.findParent(value, node.left, count + 1);
if (p == null)
{
// When need to find node value in right subtree
p = this.findParent(value, node.right, count + 1);
}
return p;
}
return null;
}
public int cousinSum(TreeNode node, TreeNode parent, int position)
{
if (node != null && node != parent && position <= this.level)
{
if (position == this.level)
{
return node.data;
}
// Sum of cousin node
return this.cousinSum(node.left, parent, position + 1) +
this.cousinSum(node.right, parent, position + 1);
}
return 0;
}
public void findCousinSum(int node)
{
Console.WriteLine("\n Given node value : " + node);
if (this.root == null)
{
Console.WriteLine("\n Empty Tree ");
return;
}
if (this.root.data == node)
{
Console.Write("Result : 0\n");
return;
}
this.level = -1;
TreeNode p = this.findParent(node, this.root, 0);
if (p == null)
{
// Given node not present
Console.WriteLine(" Result : node not exists");
}
else
{
int sum = this.cousinSum(this.root, p, 0);
// Display cousin sum
Console.WriteLine(" Result : " + sum);
}
}
public static void Main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15);
tree.addNode(13);
tree.addNode(12);
tree.addNode(14);
tree.addNode(11);
tree.addNode(20);
tree.addNode(18);
tree.addNode(19);
tree.addNode(21);
tree.addNode(22);
tree.addNode(16);
tree.addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21);
tree.findCousinSum(8);
}
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
<?php
/*
Php program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinarySearchTree
{
public $root;
public $level;
public function __construct()
{
$this->root = NULL;
$this->level = 0;
}
public function addNode($data)
{
// Create a new node
$node = new TreeNode($data);
if ($this->root == NULL)
{
// When add a first node
$this->root = $node;
}
else
{
// Get root of tree
$find = $this->root;
// Find position to insert new node
while ($find != NULL)
{
if ($find->data >= $data)
{
if ($find->left == NULL)
{
$find->left = $node;
return;
}
else
{
// Visit left sub-tree
$find = $find->left;
}
}
else
{
if ($find->right == NULL)
{
$find->right = $node;
return;
}
else
{
// Visit right sub-tree
$find = $find->right;
}
}
}
}
}
public function findParent($value, $node, $count)
{
if ($node != NULL)
{
if (($node->left != NULL && $node->left->data == $value) ||
($node->right != NULL && $node->right->data == $value))
{
// Find level of node
$this->level = $count + 1;
// Returns the parent of the data
return $node;
}
$p = NULL;
// Find node value in left subtree
$p = $this->findParent($value, $node->left, $count + 1);
if ($p == NULL)
{
// When need to find node value in right subtree
$p = $this->findParent($value, $node->right, $count + 1);
}
return $p;
}
return NULL;
}
public function cousinSum($node, $parent, $position)
{
if ($node != NULL &&
$node != $parent &&
$position <= $this->level)
{
if ($position == $this->level)
{
return $node->data;
}
// Sum of cousin node
return $this->cousinSum($node->left, $parent, $position + 1) +
$this->cousinSum($node->right, $parent, $position + 1);
}
return 0;
}
public function findCousinSum($node)
{
echo("\n Given node value : ".$node.
"\n");
if ($this->root == NULL)
{
echo("\n Empty Tree ".
"\n");
return;
}
if ($this->root->data == $node)
{
echo("Result : 0\n");
return;
}
$this->level = -1;
$p = $this->findParent($node, $this->root, 0);
if ($p == NULL)
{
// Given node not present
echo(" Result : node not exists".
"\n");
}
else
{
$sum = $this->cousinSum($this->root, $p, 0);
// Display cousin sum
echo(" Result : ".$sum.
"\n");
}
}
}
function main()
{
$tree = new BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
$tree->addNode(15);
$tree->addNode(13);
$tree->addNode(12);
$tree->addNode(14);
$tree->addNode(11);
$tree->addNode(20);
$tree->addNode(18);
$tree->addNode(19);
$tree->addNode(21);
$tree->addNode(22);
$tree->addNode(16);
$tree->addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
$tree->findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
$tree->findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
$tree->findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
$tree->findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
$tree->findCousinSum(21);
$tree->findCousinSum(8);
}
main();
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
/*
Node JS program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
constructor()
{
this.root = null;
this.level = 0;
}
addNode(data)
{
// Create a new node
var node = new TreeNode(data);
if (this.root == null)
{
// When add a first node
this.root = node;
}
else
{
// Get root of tree
var find = this.root;
// Find position to insert new node
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
findParent(value, node, count)
{
if (node != null)
{
if ((node.left != null && node.left.data == value) ||
(node.right != null && node.right.data == value))
{
// Find level of node
this.level = count + 1;
// Returns the parent of the data
return node;
}
var p = null;
// Find node value in left subtree
p = this.findParent(value, node.left, count + 1);
if (p == null)
{
// When need to find node value in right subtree
p = this.findParent(value, node.right, count + 1);
}
return p;
}
return null;
}
cousinSum(node, parent, position)
{
if (node != null && node != parent && position <= this.level)
{
if (position == this.level)
{
return node.data;
}
// Sum of cousin node
return this.cousinSum(node.left, parent, position + 1) +
this.cousinSum(node.right, parent, position + 1);
}
return 0;
}
findCousinSum(node)
{
console.log("\n Given node value : " + node);
if (this.root == null)
{
console.log("\n Empty Tree ");
return;
}
if (this.root.data == node)
{
process.stdout.write("Result : 0\n");
return;
}
this.level = -1;
var p = this.findParent(node, this.root, 0);
if (p == null)
{
// Given node not present
console.log(" Result : node not exists");
}
else
{
var sum = this.cousinSum(this.root, p, 0);
// Display cousin sum
console.log(" Result : " + sum);
}
}
}
function main()
{
var tree = new BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15);
tree.addNode(13);
tree.addNode(12);
tree.addNode(14);
tree.addNode(11);
tree.addNode(20);
tree.addNode(18);
tree.addNode(19);
tree.addNode(21);
tree.addNode(22);
tree.addNode(16);
tree.addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21);
tree.findCousinSum(8);
}
main();
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
# Python 3 program
# Sum of cousin nodes of a given node in a BST
class TreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
self.level = 0
def addNode(self, data) :
# Create a new node
node = TreeNode(data)
if (self.root == None) :
# When add a first node
self.root = node
else :
# Get root of tree
find = self.root
# Find position to insert new node
while (find != None) :
if (find.data >= data) :
if (find.left == None) :
find.left = node
return
else :
# Visit left sub-tree
find = find.left
else :
if (find.right == None) :
find.right = node
return
else :
# Visit right sub-tree
find = find.right
def findParent(self, value, node, count) :
if (node != None) :
if ((node.left != None and node.left.data == value) or
(node.right != None and node.right.data == value)) :
# Find level of node
self.level = count + 1
# Returns the parent of the data
return node
p = None
# Find node value in left subtree
p = self.findParent(value, node.left, count + 1)
if (p == None) :
# When need to find node value in right subtree
p = self.findParent(value, node.right, count + 1)
return p
return None
def cousinSum(self, node, parent, position) :
if (node != None and node != parent and position <= self.level) :
if (position == self.level) :
return node.data
# Sum of cousin node
return self.cousinSum(node.left, parent, position + 1) \
+ self.cousinSum(node.right, parent, position + 1)
return 0
def findCousinSum(self, node) :
print("\n Given node value : ", node)
if (self.root == None) :
print("\n Empty Tree ")
return
if (self.root.data == node) :
print("Result : 0")
return
self.level = -1
p = self.findParent(node, self.root, 0)
if (p == None) :
# Given node not present
print(" Result : node not exists")
else :
sum = self.cousinSum(self.root, p, 0)
# Display cousin sum
print(" Result : ", sum)
def main() :
tree = BinarySearchTree()
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Binary search tree
# Add node
tree.addNode(15)
tree.addNode(13)
tree.addNode(12)
tree.addNode(14)
tree.addNode(11)
tree.addNode(20)
tree.addNode(18)
tree.addNode(19)
tree.addNode(21)
tree.addNode(22)
tree.addNode(16)
tree.addNode(17)
# Test A
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 → 18 21 ←
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 14
# Cousin : [18 + 21] = 39
tree.findCousinSum(14)
# Test B
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 18 21
# / / \ \
# → 11 → 16 → 19 22
# \
# 17
# -----------------------
# Node : 22
# Cousin : [11 + 16 + 19] = 46
tree.findCousinSum(22)
# Test C
# 15
# / \
# / \
# / \
# 13 20 ←
# / \ / \
# 12 14 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 17
# Cousin : None = 0
tree.findCousinSum(17)
# Test D
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 13
# Cousin : None = 0
tree.findCousinSum(13)
# Test E
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# → 12 14 ← 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 21
# Cousin : [12 + 14] = 26
tree.findCousinSum(21)
tree.findCousinSum(8)
if __name__ == "__main__": main()
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
# Ruby program
# Sum of cousin nodes of a given node in a BST
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
class BinarySearchTree
# Define the accessor and reader of class BinarySearchTree
attr_reader :root, :level
attr_accessor :root, :level
def initialize()
self.root = nil
self.level = 0
end
def addNode(data)
# Create a new node
node = TreeNode.new(data)
if (self.root == nil)
# When add a first node
self.root = node
else
# Get root of tree
find = self.root
# Find position to insert new node
while (find != nil)
if (find.data >= data)
if (find.left == nil)
find.left = node
return
else
# Visit left sub-tree
find = find.left
end
else
if (find.right == nil)
find.right = node
return
else
# Visit right sub-tree
find = find.right
end
end
end
end
end
def findParent(value, node, count)
if (node != nil)
if ((node.left != nil && node.left.data == value) ||
(node.right != nil && node.right.data == value))
# Find level of node
self.level = count + 1
# Returns the parent of the data
return node
end
p = nil
# Find node value in left subtree
p = self.findParent(value, node.left, count + 1)
if (p == nil)
# When need to find node value in right subtree
p = self.findParent(value, node.right, count + 1)
end
return p
end
return nil
end
def cousinSum(node, parent, position)
if (node != nil && node != parent && position <= self.level)
if (position == self.level)
return node.data
end
# Sum of cousin node
return self.cousinSum(node.left, parent, position + 1) +
self.cousinSum(node.right, parent, position + 1)
end
return 0
end
def findCousinSum(node)
print("\n Given node value : ", node, "\n")
if (self.root == nil)
print("\n Empty Tree ", "\n")
return
end
if (self.root.data == node)
print("Result : 0\n")
return
end
self.level = -1
p = self.findParent(node, self.root, 0)
if (p == nil)
# Given node not present
print(" Result : node not exists", "\n")
else
sum = self.cousinSum(self.root, p, 0)
# Display cousin sum
print(" Result : ", sum, "\n")
end
end
end
def main()
tree = BinarySearchTree.new()
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Binary search tree
# Add node
tree.addNode(15)
tree.addNode(13)
tree.addNode(12)
tree.addNode(14)
tree.addNode(11)
tree.addNode(20)
tree.addNode(18)
tree.addNode(19)
tree.addNode(21)
tree.addNode(22)
tree.addNode(16)
tree.addNode(17)
# Test A
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 → 18 21 ←
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 14
# Cousin : [18 + 21] = 39
tree.findCousinSum(14)
# Test B
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 18 21
# / / \ \
# → 11 → 16 → 19 22
# \
# 17
# -----------------------
# Node : 22
# Cousin : [11 + 16 + 19] = 46
tree.findCousinSum(22)
# Test C
# 15
# / \
# / \
# / \
# 13 20 ←
# / \ / \
# 12 14 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 17
# Cousin : None = 0
tree.findCousinSum(17)
# Test D
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 13
# Cousin : None = 0
tree.findCousinSum(13)
# Test E
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# → 12 14 ← 18 21
# / / \ \
# 11 16 19 22
# \
# 17
# -----------------------
# Node : 21
# Cousin : [12 + 14] = 26
tree.findCousinSum(21)
tree.findCousinSum(8)
end
main()
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
/*
Scala program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinarySearchTree(var root: TreeNode,
var level: Int)
{
def this()
{
this(null, 0);
}
def addNode(data: Int): Unit = {
// Create a new node
var node: TreeNode = new TreeNode(data);
if (this.root == null)
{
// When add a first node
this.root = node;
}
else
{
// Get root of tree
var find: TreeNode = this.root;
// Find position to insert new node
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
def findParent(value: Int, node: TreeNode, count: Int): TreeNode = {
if (node != null)
{
if ((node.left != null && node.left.data == value) ||
(node.right != null && node.right.data == value))
{
// Find level of node
this.level = count + 1;
// Returns the parent of the data
return node;
}
var p: TreeNode = null;
// Find node value in left subtree
p = findParent(value, node.left, count + 1);
if (p == null)
{
// When need to find node value in right subtree
p = findParent(value, node.right, count + 1);
}
return p;
}
return null;
}
def cousinSum(node: TreeNode, parent: TreeNode, position: Int): Int = {
if (node != null && node != parent && position <= this.level)
{
if (position == this.level)
{
return node.data;
}
// Sum of cousin node
return cousinSum(node.left, parent, position + 1) +
cousinSum(node.right, parent, position + 1);
}
return 0;
}
def findCousinSum(node: Int): Unit = {
println("\n Given node value : " + node);
if (this.root == null)
{
println("\n Empty Tree ");
return;
}
if (this.root.data == node)
{
print("Result : 0\n");
return;
}
this.level = -1;
var p: TreeNode = findParent(node, root, 0);
if (p == null)
{
// Given node not present
println(" Result : node not exists");
}
else
{
var sum: Int = cousinSum(this.root, p, 0);
// Display cousin sum
println(" Result : " + sum);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinarySearchTree = new BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15);
tree.addNode(13);
tree.addNode(12);
tree.addNode(14);
tree.addNode(11);
tree.addNode(20);
tree.addNode(18);
tree.addNode(19);
tree.addNode(21);
tree.addNode(22);
tree.addNode(16);
tree.addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21);
tree.findCousinSum(8);
}
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
/*
Swift 4 program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree
{
var root: TreeNode? ;
var level: Int;
init()
{
self.root = nil;
self.level = 0;
}
func addNode(_ data: Int)
{
// Create a new node
let node: TreeNode = TreeNode(data);
if (self.root == nil)
{
// When add a first node
self.root = node;
}
else
{
// Get root of tree
var find: TreeNode? = self.root;
// Find position to insert new node
while (find != nil)
{
if (find!.data >= data)
{
if (find!.left == nil)
{
find!.left = node;
return;
}
else
{
// Visit left sub-tree
find = find!.left;
}
}
else
{
if (find!.right == nil)
{
find!.right = node;
return;
}
else
{
// Visit right sub-tree
find = find!.right;
}
}
}
}
}
func findParent(_ value: Int,
_ node: TreeNode? ,
_ count : Int) -> TreeNode?
{
if (node != nil)
{
if ((node!.left != nil && node!.left!.data == value) ||
(node!.right != nil && node!.right!.data == value))
{
// Find level of node
self.level = count + 1;
// Returns the parent of the data
return node;
}
// Find node value in left subtree
var p : TreeNode? = self.findParent(value, node!.left, count + 1);
if (p == nil)
{
// When need to find node value in right subtree
p = self.findParent(value, node!.right, count + 1);
}
return p;
}
return nil;
}
func cousinSum(_ node: TreeNode? ,
_ parent : TreeNode? ,
_ position : Int) -> Int
{
if (node != nil && !(node === parent) && position <= self.level)
{
if (position == self.level)
{
return node!.data;
}
// Sum of cousin node
return self.cousinSum(node!.left, parent, position + 1) +
self.cousinSum(node!.right, parent, position + 1);
}
return 0;
}
func findCousinSum(_ node: Int)
{
print("\n Given node value : ", node);
if (self.root == nil)
{
print("\n Empty Tree ");
return;
}
if (self.root!.data == node)
{
print("Result : 0");
return;
}
self.level = -1;
let p: TreeNode? = self.findParent(node, self.root, 0);
if (p == nil)
{
// Given node not present
print(" Result : node not exists");
}
else
{
let sum: Int = self.cousinSum(self.root, p, 0);
// Display cousin sum
print(" Result : ", sum);
}
}
}
func main()
{
let tree: BinarySearchTree = BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15);
tree.addNode(13);
tree.addNode(12);
tree.addNode(14);
tree.addNode(11);
tree.addNode(20);
tree.addNode(18);
tree.addNode(19);
tree.addNode(21);
tree.addNode(22);
tree.addNode(16);
tree.addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21);
tree.findCousinSum(8);
}
main();
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
/*
Kotlin program
Sum of cousin nodes of a given node in a BST
*/
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
var root: TreeNode ? ;
var level: Int;
constructor()
{
this.root = null;
this.level = 0;
}
fun addNode(data: Int): Unit
{
// Create a new node
val node: TreeNode = TreeNode(data);
if (this.root == null)
{
// When add a first node
this.root = node;
}
else
{
// Get root of tree
var find: TreeNode ? = this.root;
// Find position to insert new node
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
fun findParent(value: Int, node: TreeNode ? , count : Int): TreeNode ?
{
if (node != null)
{
if ((node.left != null && node.left?.data == value) ||
(node.right != null && node.right?.data == value))
{
// Find level of node
this.level = count + 1;
// Returns the parent of the data
return node;
}
// Find node value in left subtree
var p: TreeNode? = this.findParent(value, node.left, count + 1);
if (p == null)
{
// When need to find node value in right subtree
p = this.findParent(value, node.right, count + 1);
}
return p;
}
return null;
}
fun cousinSum(node: TreeNode ? ,
parent : TreeNode ? , position : Int): Int
{
if (node != null && node != parent && position <= this.level)
{
if (position == this.level)
{
return node.data;
}
// Sum of cousin node
return this.cousinSum(node.left, parent, position + 1) +
this.cousinSum(node.right, parent, position + 1);
}
return 0;
}
fun findCousinSum(node: Int): Unit
{
println("\n Given node value : " + node);
if (this.root == null)
{
println("\n Empty Tree ");
return;
}
if (this.root!!.data == node)
{
print("Result : 0\n");
return;
}
this.level = -1;
var p: TreeNode? = this.findParent(node, this.root, 0);
if (p == null)
{
// Given node not present
println(" Result : node not exists");
}
else
{
val sum: Int = this.cousinSum(this.root, p, 0);
// Display cousin sum
println(" Result : " + sum);
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinarySearchTree = BinarySearchTree();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Binary search tree
*/
// Add node
tree.addNode(15);
tree.addNode(13);
tree.addNode(12);
tree.addNode(14);
tree.addNode(11);
tree.addNode(20);
tree.addNode(18);
tree.addNode(19);
tree.addNode(21);
tree.addNode(22);
tree.addNode(16);
tree.addNode(17);
// Test A
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 → 18 21 ←
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 14
Cousin : [18 + 21] = 39
*/
tree.findCousinSum(14);
// Test B
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
→ 11 → 16 → 19 22
\
17
-----------------------
Node : 22
Cousin : [11 + 16 + 19] = 46
*/
tree.findCousinSum(22);
// Test C
/*
15
/ \
/ \
/ \
13 20 ←
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 17
Cousin : None = 0
*/
tree.findCousinSum(17);
// Test D
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 13
Cousin : None = 0
*/
tree.findCousinSum(13);
// Test E
/*
15
/ \
/ \
/ \
13 20
/ \ / \
→ 12 14 ← 18 21
/ / \ \
11 16 19 22
\
17
-----------------------
Node : 21
Cousin : [12 + 14] = 26
*/
tree.findCousinSum(21);
tree.findCousinSum(8);
}
Output
Given node value : 14
Result : 39
Given node value : 22
Result : 46
Given node value : 17
Result : 0
Given node value : 13
Result : 0
Given node value : 21
Result : 26
Given node value : 8
Result : node not exists
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.
New Comment