Find the Sum of all full nodes in a Binary Tree
Here given code implementation process.
/*
C Program
Sum of all full nodes in a Binary Tree
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
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;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Display pre order elements
void preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
int sum_full_nodes(struct Node *node)
{
int sum = 0;
if (node != NULL)
{
if (node->left != NULL && node->right != NULL)
{
sum = node->data;
}
// Calculate node sum
sum += sum_full_nodes(node->left) + sum_full_nodes(node->right);
}
return sum;
}
int main()
{
struct Node *root = NULL;
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
root = get_node(6);
root->left = get_node(7);
root->left->right = get_node(8);
root->left->right->right = get_node(1);
root->left->right->right->left = get_node(9);
root->left->right->left = get_node(1);
root->right = get_node(3);
root->right->left = get_node(2);
root->right->right = get_node(1);
root->right->right->right = get_node(5);
root->right->right->left = get_node(4);
//Display Tree Element
printf("\n Tree Nodes : ");
preorder(root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
//Display Calculated Result
printf("\n Full node sum is : %d \n", sum_full_nodes(root));
return 0;
}
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
/*
Java Program
Sum of all full nodes in a Binary Tree
*/
//Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
}
//Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
public int sum_full_nodes(Node node)
{
int sum = 0;
if (node != null)
{
if (node.left != null && node.right != null)
{
sum = node.data;
}
// Calculate node sum
sum += sum_full_nodes(node.left) + sum_full_nodes(node.right);
}
return sum;
}
public static void main(String[] args)
{
//Make object of binary tree
BinaryTree tree = new BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
tree.root = new Node(6);
tree.root.left = new Node(7);
tree.root.left.right = new Node(8);
tree.root.left.right.right = new Node(1);
tree.root.left.right.right.left = new Node(9);
tree.root.left.right.left = new Node(1);
tree.root.right = new Node(3);
tree.root.right.left = new Node(2);
tree.root.right.right = new Node(1);
tree.root.right.right.right = new Node(5);
tree.root.right.right.left = new Node(4);
//Display Tree Element
System.out.print("\n Tree Nodes : ");
tree.preorder(tree.root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
//Display Calculated Result
System.out.print("\n Full node sum is : " + tree.sum_full_nodes(tree.root) + " \n");
}
}
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Sum of all full nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
// set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: Node *root;
BinaryTree()
{
// Set initial tree root to null
this->root = NULL;
}
// Display pre order elements
void preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
int sum_full_nodes(Node *node)
{
int sum = 0;
if (node != NULL)
{
if (node->left != NULL && node->right != NULL)
{
sum = node->data;
}
// Calculate node sum
sum += this->sum_full_nodes(node->left) + this->sum_full_nodes(node->right);
}
return sum;
}
};
int main()
{
// Make object of binary tree
BinaryTree tree = BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
tree.root = new Node(6);
tree.root->left = new Node(7);
tree.root->left->right = new Node(8);
tree.root->left->right->right = new Node(1);
tree.root->left->right->right->left = new Node(9);
tree.root->left->right->left = new Node(1);
tree.root->right = new Node(3);
tree.root->right->left = new Node(2);
tree.root->right->right = new Node(1);
tree.root->right->right->right = new Node(5);
tree.root->right->right->left = new Node(4);
// Display Tree Element
cout << "\n Tree Nodes : ";
tree.preorder(tree.root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
// Display Calculated Result
cout << "\n Full node sum is : " << tree.sum_full_nodes(tree.root) << " \n";
return 0;
}
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
//Include namespace system
using System;
/*
C# Program
Sum of all full nodes in a Binary Tree
*/
// Binary Tree node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public Node root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
public int sum_full_nodes(Node node)
{
int sum = 0;
if (node != null)
{
if (node.left != null && node.right != null)
{
sum = node.data;
}
// Calculate node sum
sum += sum_full_nodes(node.left) + sum_full_nodes(node.right);
}
return sum;
}
public static void Main(String[] args)
{
// Make object of binary tree
BinaryTree tree = new BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
tree.root = new Node(6);
tree.root.left = new Node(7);
tree.root.left.right = new Node(8);
tree.root.left.right.right = new Node(1);
tree.root.left.right.right.left = new Node(9);
tree.root.left.right.left = new Node(1);
tree.root.right = new Node(3);
tree.root.right.left = new Node(2);
tree.root.right.right = new Node(1);
tree.root.right.right.right = new Node(5);
tree.root.right.right.left = new Node(4);
// Display Tree Element
Console.Write("\n Tree Nodes : ");
tree.preorder(tree.root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
// Display Calculated Result
Console.Write("\n Full node sum is : " + tree.sum_full_nodes(tree.root) + " \n");
}
}
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
<?php
/*
Php Program
Sum of all full nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
// set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
function __construct()
{
// Set initial tree root to null
$this->root = null;
}
// Display pre order elements
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
public function sum_full_nodes($node)
{
$sum = 0;
if ($node != null)
{
if ($node->left != null && $node->right != null)
{
$sum = $node->data;
}
// Calculate node sum
$sum += $this->sum_full_nodes($node->left) + $this->sum_full_nodes($node->right);
}
return $sum;
}
}
function main()
{
// Make object of binary tree
$tree = new BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
$tree->root = new Node(6);
$tree->root->left = new Node(7);
$tree->root->left->right = new Node(8);
$tree->root->left->right->right = new Node(1);
$tree->root->left->right->right->left = new Node(9);
$tree->root->left->right->left = new Node(1);
$tree->root->right = new Node(3);
$tree->root->right->left = new Node(2);
$tree->root->right->right = new Node(1);
$tree->root->right->right->right = new Node(5);
$tree->root->right->right->left = new Node(4);
// Display Tree Element
echo "\n Tree Nodes : ";
$tree->preorder($tree->root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
// Display Calculated Result
echo "\n Full node sum is : ". $tree->sum_full_nodes($tree->root) ." \n";
}
main();
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
/*
Node Js Program
Sum of all full nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
constructor(data)
{
// set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
// Set initial tree root to null
this.root = null;
}
// Display pre order elements
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
sum_full_nodes(node)
{
var sum = 0;
if (node != null)
{
if (node.left != null && node.right != null)
{
sum = node.data;
}
// Calculate node sum
sum += this.sum_full_nodes(node.left) + this.sum_full_nodes(node.right);
}
return sum;
}
}
function main()
{
// Make object of binary tree
var tree = new BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
tree.root = new Node(6);
tree.root.left = new Node(7);
tree.root.left.right = new Node(8);
tree.root.left.right.right = new Node(1);
tree.root.left.right.right.left = new Node(9);
tree.root.left.right.left = new Node(1);
tree.root.right = new Node(3);
tree.root.right.left = new Node(2);
tree.root.right.right = new Node(1);
tree.root.right.right.right = new Node(5);
tree.root.right.right.left = new Node(4);
// Display Tree Element
process.stdout.write("\n Tree Nodes : ");
tree.preorder(tree.root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
// Display Calculated Result
process.stdout.write("\n Full node sum is : " + tree.sum_full_nodes(tree.root) + " \n");
}
main();
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
# Python 3 Program
# Sum of all full nodes in a Binary Tree
# Binary Tree node
class Node :
def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
# Set initial tree root to null
self.root = None
# Display pre order elements
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
# Calculate sum of all full nodes in binary tree.
# All nodes which is containing both left and right child
def sum_full_nodes(self, node) :
sum = 0
if (node != None) :
if (node.left != None and node.right != None) :
sum = node.data
# Calculate node sum
sum += self.sum_full_nodes(node.left) + self.sum_full_nodes(node.right)
return sum
def main() :
# Make object of binary tree
tree = BinaryTree()
#
# constructor binary tree
# -----------------------
# 6
# / \
# / \
# 7 3
# \ / \
# 8 2 1
# / \ / \
# 1 1 4 5
# /
# 9
# -----------------------
#
tree.root = Node(6)
tree.root.left = Node(7)
tree.root.left.right = Node(8)
tree.root.left.right.right = Node(1)
tree.root.left.right.right.left = Node(9)
tree.root.left.right.left = Node(1)
tree.root.right = Node(3)
tree.root.right.left = Node(2)
tree.root.right.right = Node(1)
tree.root.right.right.right = Node(5)
tree.root.right.right.left = Node(4)
# Display Tree Element
print("\n Tree Nodes : ", end = "")
tree.preorder(tree.root)
#
# 6
# / \
# / \
# 7 3
# \ / \
# 8 2 1
# / \ / \
# 1 1 4 5
# /
# 9
# -----------------------
# Full nodes [6,8,3,1]
# [ Both left and right child exists ]
#
# 6
# / \
# 7 3
# --------
# 8
# / \
# 1 1
# -------
# 3
# / \
# 2 1
# ------
# 1
# / \
# 4 5
#
# Display Calculated Result
print("\n Full node sum is : ", tree.sum_full_nodes(tree.root) ," \n", end = "")
if __name__ == "__main__": main()
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
# Ruby Program
# Sum of all full nodes in a Binary Tree
# Binary Tree node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
# Set initial tree root to null
self.root = nil
end
# Display pre order elements
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
# Calculate sum of all full nodes in binary tree.
# All nodes which is containing both left and right child
def sum_full_nodes(node)
sum = 0
if (node != nil)
if (node.left != nil && node.right != nil)
sum = node.data
end
# Calculate node sum
sum += self.sum_full_nodes(node.left) + self.sum_full_nodes(node.right)
end
return sum
end
end
def main()
# Make object of binary tree
tree = BinaryTree.new()
#
# constructor binary tree
# -----------------------
# 6
# / \
# / \
# 7 3
# \ / \
# 8 2 1
# / \ / \
# 1 1 4 5
# /
# 9
# -----------------------
#
tree.root = Node.new(6)
tree.root.left = Node.new(7)
tree.root.left.right = Node.new(8)
tree.root.left.right.right = Node.new(1)
tree.root.left.right.right.left = Node.new(9)
tree.root.left.right.left = Node.new(1)
tree.root.right = Node.new(3)
tree.root.right.left = Node.new(2)
tree.root.right.right = Node.new(1)
tree.root.right.right.right = Node.new(5)
tree.root.right.right.left = Node.new(4)
# Display Tree Element
print("\n Tree Nodes : ")
tree.preorder(tree.root)
#
# 6
# / \
# / \
# 7 3
# \ / \
# 8 2 1
# / \ / \
# 1 1 4 5
# /
# 9
# -----------------------
# Full nodes [6,8,3,1]
# [ Both left and right child exists ]
#
# 6
# / \
# 7 3
# --------
# 8
# / \
# 1 1
# -------
# 3
# / \
# 2 1
# ------
# 1
# / \
# 4 5
#
# Display Calculated Result
print("\n Full node sum is : ", tree.sum_full_nodes(tree.root) ," \n")
end
main()
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
/*
Scala Program
Sum of all full nodes in a Binary Tree
*/
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: Node)
{
def this()
{
this(null);
}
// Display pre order elements
def preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
def sum_full_nodes(node: Node): Int = {
var sum: Int = 0;
if (node != null)
{
if (node.left != null && node.right != null)
{
sum = node.data;
}
// Calculate node sum
sum += sum_full_nodes(node.left) + sum_full_nodes(node.right);
}
return sum;
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Make object of binary tree
var tree: BinaryTree = new BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
tree.root = new Node(6);
tree.root.left = new Node(7);
tree.root.left.right = new Node(8);
tree.root.left.right.right = new Node(1);
tree.root.left.right.right.left = new Node(9);
tree.root.left.right.left = new Node(1);
tree.root.right = new Node(3);
tree.root.right.left = new Node(2);
tree.root.right.right = new Node(1);
tree.root.right.right.right = new Node(5);
tree.root.right.right.left = new Node(4);
// Display Tree Element
print("\n Tree Nodes : ");
tree.preorder(tree.root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1]
[ Both left and right child exists ]
6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
// Display Calculated Result
print("\n Full node sum is : " + tree.sum_full_nodes(tree.root) + " \n");
}
}
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
/*
Swift 4 Program
Sum of all full nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
// set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: Node? ;
init()
{
// Set initial tree root to null
self.root = nil;
}
// Display pre order elements
func preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// Calculate sum of all full nodes in binary tree.
// All nodes which is containing both left and right child
func sum_full_nodes(_ node: Node? )->Int
{
var sum: Int = 0;
if (node != nil)
{
if (node!.left != nil && node!.right != nil)
{
sum = node!.data;
}
// Calculate node sum
sum += self.sum_full_nodes(node!.left) + self.sum_full_nodes(node!.right);
}
return sum;
}
}
func main()
{
// Make object of binary tree
let tree: BinaryTree = BinaryTree();
/*
constructor binary tree
-----------------------
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
*/
tree.root = Node(6);
tree.root!.left = Node(7);
tree.root!.left!.right = Node(8);
tree.root!.left!.right!.right = Node(1);
tree.root!.left!.right!.right!.left = Node(9);
tree.root!.left!.right!.left = Node(1);
tree.root!.right = Node(3);
tree.root!.right!.left = Node(2);
tree.root!.right!.right = Node(1);
tree.root!.right!.right!.right = Node(5);
tree.root!.right!.right!.left = Node(4);
// Display Tree Element
print("\n Tree Nodes : ", terminator: "");
tree.preorder(tree.root);
/*
6
/ \
/ \
7 3
\ / \
8 2 1
/ \ / \
1 1 4 5
/
9
-----------------------
Full nodes [6,8,3,1][Both left and right child exists ]6
/ \
7 3
--------
8
/ \
1 1
-------
3
/ \
2 1
------
1
/ \
4 5
*/
// Display Calculated Result
print("\n Full node sum is : ", tree.sum_full_nodes(tree.root) ," \n", terminator: "");
}
main();
Output
Tree Nodes : 6 7 8 1 1 9 3 2 1 4 5
Full node sum is : 18
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