Escriba una función que devuelva verdadero si el árbol binario dado es SumTree, de lo contrario, es falso. Un SumTree es un árbol binario donde el valor de un Node es igual a la suma de los Nodes presentes en su subárbol izquierdo y subárbol derecho. Un árbol vacío es SumTree y la suma de un árbol vacío se puede considerar como 0. Un Node hoja también se considera como SumTree.
El siguiente es un ejemplo de SumTree.
26
/ \
10 3
/ \ \
4 6 3
Método 1 (Simple)
Obtenga la suma de los Nodes en el subárbol izquierdo y el subárbol derecho. Compruebe si la suma calculada es igual a los datos de la raíz. Además, verifique recursivamente si los subárboles izquierdo y derecho son SumTrees.
C++
// C++ program to check if Binary tree
// is sum tree or not
#include <iostream>
using namespace std;
// A binary tree node has data,
// left child and right child
struct node
{
int data;
struct node* left;
struct node* right;
};
// A utility function to get the sum
// of values in tree with root as root
int sum(struct node *root)
{
if (root == NULL)
return 0;
return sum(root->left) + root->data +
sum(root->right);
}
// Returns 1 if sum property holds for
// the given node and both of its children
int isSumTree(struct node* node)
{
int ls, rs;
// If node is NULL or it's a leaf
// node then return true
if (node == NULL ||
(node->left == NULL &&
node->right == NULL))
return 1;
// Get sum of nodes in left and
// right subtrees
ls = sum(node->left);
rs = sum(node->right);
// If the node and both of its
// children satisfy the property
// return 1 else 0
if ((node->data == ls + rs) &&
isSumTree(node->left) &&
isSumTree(node->right))
return 1;
return 0;
}
// Helper function that allocates a new node
// with the given data and NULL left and right
// pointers.
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(
sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// Driver code
int main()
{
struct node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if (isSumTree(root))
cout << "The given tree is a SumTree ";
else
cout << "The given tree is not a SumTree ";
getchar();
return 0;
}
// This code is contributed by khushboogoyal499
C
// C program to check if Binary tree
// is sum tree or not
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, left child and right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* A utility function to get the sum of values in tree with root
as root */
int sum(struct node *root)
{
if(root == NULL)
return 0;
return sum(root->left) + root->data + sum(root->right);
}
/* returns 1 if sum property holds for the given
node and both of its children */
int isSumTree(struct node* node)
{
int ls, rs;
/* If node is NULL or it's a leaf node then
return true */
if(node == NULL ||
(node->left == NULL && node->right == NULL))
return 1;
/* Get sum of nodes in left and right subtrees */
ls = sum(node->left);
rs = sum(node->right);
/* if the node and both of its children satisfy the
property return 1 else 0*/
if((node->data == ls + rs)&&
isSumTree(node->left) &&
isSumTree(node->right))
return 1;
return 0;
}
/*
Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* newNode(int data)
{
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above function */
int main()
{
struct node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if(isSumTree(root))
printf("The given tree is a SumTree.");
else
printf("The given tree is not a SumTree.");
getchar();
return 0;
}
Java
// Java program to check if Binary tree
// is sum tree or not
import java.io.*;
// A binary tree node has data,
// left child and right child
class Node
{
int data;
Node left, right, nextRight;
// Helper function that allocates a new node
// with the given data and NULL left and right
// pointers.
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
public static Node root;
// A utility function to get the sum
// of values in tree with root as root
static int sum(Node node)
{
if(node == null)
{
return 0;
}
return (sum(node.left) + node.data+sum(node.right));
}
// Returns 1 if sum property holds for
// the given node and both of its children
static int isSumTree(Node node)
{
int ls,rs;
// If node is NULL or it's a leaf
// node then return true
if(node == null || (node.left == null && node.right == null))
{
return 1;
}
// Get sum of nodes in left and
// right subtrees
ls = sum(node.left);
rs = sum(node.right);
// If the node and both of its
// children satisfy the property
// return 1 else 0
if((node.data == ls + rs) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
return 1;
}
return 0;
}
// Driver code
public static void main (String[] args)
{
BinaryTree tree=new BinaryTree();
tree.root=new Node(26);
tree.root.left=new Node(10);
tree.root.right=new Node(3);
tree.root.left.left=new Node(4);
tree.root.left.right=new Node(6);
tree.root.right.right=new Node(3);
if(isSumTree(root) != 0)
{
System.out.println("The given tree is a SumTree");
}
else
{
System.out.println("The given tree is not a SumTree");
}
}
}
// This code is contributed by rag2127
Python3
# Python3 program to implement
# the above approach
# A binary tree node has data,
# left child and right child
class node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# A utility function to get the sum
# of values in tree with root as root
def sum(root):
if(root == None):
return 0
return (sum(root.left) +
root.data +
sum(root.right))
# returns 1 if sum property holds
# for the given node and both of
# its children
def isSumTree(node):
# ls, rs
# If node is None or it's a leaf
# node then return true
if(node == None or
(node.left == None and
node.right == None)):
return 1
# Get sum of nodes in left and
# right subtrees
ls = sum(node.left)
rs = sum(node.right)
# if the node and both of its children
# satisfy the property return 1 else 0
if((node.data == ls + rs) and
isSumTree(node.left) and
isSumTree(node.right)):
return 1
return 0
# Driver code
if __name__ == '__main__':
root = node(26)
root.left= node(10)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(6)
root.right.right = node(3)
if(isSumTree(root)):
print("The given tree is a SumTree ")
else:
print("The given tree is not a SumTree ")
# This code is contributed by Mohit Kumar 29
C#
// C# program to check if Binary tree
// is sum tree or not
using System;
// A binary tree node has data,
// left child and right child
public class Node
{
public int data;
public Node left, right, nextRight;
// Helper function that allocates a new node
// with the given data and NULL left and right
// pointers.
public Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
public Node root;
// A utility function to get the sum
// of values in tree with root as root
int sum(Node node)
{
if(node == null)
{
return 0;
}
return (sum(node.left) + node.data+sum(node.right));
}
// Returns 1 if sum property holds for
// the given node and both of its children
int isSumTree(Node node)
{
int ls,rs;
// If node is NULL or it's a leaf
// node then return true
if(node == null || (node.left == null && node.right == null))
{
return 1;
}
// Get sum of nodes in left and
// right subtrees
ls = sum(node.left);
rs = sum(node.right);
// If the node and both of its
// children satisfy the property
// return 1 else 0
if((node.data == ls + rs) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
return 1;
}
return 0;
}
// Driver code
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(26);
tree.root.left = new Node(10);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(6);
tree.root.right.right = new Node(3);
if(tree.isSumTree(tree.root) != 0)
{
Console.WriteLine("The given tree is a SumTree");
}
else
{
Console.WriteLine("The given tree is not a SumTree");
}
}
}
// This code is contributed by Pratham76
Javascript
<script>
// Javascript program to check if Binary tree
// is sum tree or not
// A binary tree node has data,
// left child and right child
class Node
{
// Helper function that allocates a new node
// with the given data and NULL left and right
// pointers.
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
let root;
// A utility function to get the sum
// of values in tree with root as root
function sum(node)
{
if(node == null)
{
return 0;
}
return (sum(node.left) + node.data+sum(node.right));
}
// Returns 1 if sum property holds for
// the given node and both of its children
function isSumTree(node)
{
let ls,rs;
// If node is NULL or it's a leaf
// node then return true
if(node == null || (node.left == null && node.right == null))
{
return 1;
}
// Get sum of nodes in left and
// right subtrees
ls = sum(node.left);
rs = sum(node.right);
// If the node and both of its
// children satisfy the property
// return 1 else 0
if((node.data == ls + rs) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
return 1;
}
return 0;
}
// Driver code
root = new Node(26)
root.left= new Node(10)
root.right = new Node(3)
root.left.left = new Node(4)
root.left.right = new Node(6)
root.right.right = new Node(3)
if(isSumTree(root) != 0)
{
document.write("The given tree is a SumTree");
}
else
{
document.write("The given tree is not a SumTree");
}
// This code is contributed by unknown2108
</script>
Producción
The given tree is a SumTree
Complejidad temporal: O(n 2 ) en el peor de los casos. El peor de los casos ocurre con un árbol sesgado.
Espacio auxiliar: O(n) para espacio de pila
Método 2 (complicado)
El método 1 usa sum() para obtener la suma de los Nodes en los subárboles izquierdo y derecho. El método 2 usa las siguientes reglas para obtener la suma directamente.
1) Si el Node es un Node hoja, la suma del subárbol enraizado con este Node es igual al valor de este Node.
2) Si el Node no es un Node hoja, la suma del subárbol enraizado con este Node es el doble del valor de este Node (suponiendo que el árbol enraizado con este Node sea SumTree).
C++
// C++ program to check if Binary tree
// is sum tree or not
#include<bits/stdc++.h>
using namespace std;
/* A binary tree node has data,
left child and right child */
struct node
{
int data;
node* left;
node* right;
};
/* Utility function to check if
the given node is leaf or not */
int isLeaf(node *node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
return 0;
}
/* returns 1 if SumTree property holds for the given
tree */
int isSumTree(node* node)
{
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
/* If node is NULL or it's a leaf node then
return true */
if(node == NULL || isLeaf(node))
return 1;
if( isSumTree(node->left) && isSumTree(node->right))
{
// Get the sum of nodes in left subtree
if(node->left == NULL)
ls = 0;
else if(isLeaf(node->left))
ls = node->left->data;
else
ls = 2 * (node->left->data);
// Get the sum of nodes in right subtree
if(node->right == NULL)
rs = 0;
else if(isLeaf(node->right))
rs = node->right->data;
else
rs = 2 * (node->right->data);
/* If root's data is equal to sum of nodes in left
and right subtrees then return 1 else return 0*/
return(node->data == ls + rs);
}
return 0;
}
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
node* newNode(int data)
{
node* node1 = new node();
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return(node1);
}
/* Driver code */
int main()
{
node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if(isSumTree(root))
cout << "The given tree is a SumTree ";
else
cout << "The given tree is not a SumTree ";
return 0;
}
// This code is contributed by rutvik_56
C
// C program to check if Binary tree
// is sum tree or not
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data,
left child and right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Utility function to check if the given node is leaf or not */
int isLeaf(struct node *node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
return 0;
}
/* returns 1 if SumTree property holds for the given
tree */
int isSumTree(struct node* node)
{
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
/* If node is NULL or it's a leaf node then
return true */
if(node == NULL || isLeaf(node))
return 1;
if( isSumTree(node->left) && isSumTree(node->right))
{
// Get the sum of nodes in left subtree
if(node->left == NULL)
ls = 0;
else if(isLeaf(node->left))
ls = node->left->data;
else
ls = 2*(node->left->data);
// Get the sum of nodes in right subtree
if(node->right == NULL)
rs = 0;
else if(isLeaf(node->right))
rs = node->right->data;
else
rs = 2*(node->right->data);
/* If root's data is equal to sum of nodes in left
and right subtrees then return 1 else return 0*/
return(node->data == ls + rs);
}
return 0;
}
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* newNode(int data)
{
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above function */
int main()
{
struct node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if(isSumTree(root))
printf("The given tree is a SumTree ");
else
printf("The given tree is not a SumTree ");
getchar();
return 0;
}
Java
// Java program to check if Binary tree is sum tree or not
/* A binary tree node has data, left child and right child */
class Node
{
int data;
Node left, right, nextRight;
Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
class BinaryTree
{
Node root;
/* Utility function to check if the given node is leaf or not */
int isLeaf(Node node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
return 0;
}
/* returns 1 if SumTree property holds for the given
tree */
int isSumTree(Node node)
{
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
/* If node is NULL or it's a leaf node then
return true */
if (node == null || isLeaf(node) == 1)
return 1;
if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
// Get the sum of nodes in left subtree
if (node.left == null)
ls = 0;
else if (isLeaf(node.left) != 0)
ls = node.left.data;
else
ls = 2 * (node.left.data);
// Get the sum of nodes in right subtree
if (node.right == null)
rs = 0;
else if (isLeaf(node.right) != 0)
rs = node.right.data;
else
rs = 2 * (node.right.data);
/* If root's data is equal to sum of nodes in left
and right subtrees then return 1 else return 0*/
if ((node.data == rs + ls))
return 1;
else
return 0;
}
return 0;
}
/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(26);
tree.root.left = new Node(10);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(6);
tree.root.right.right = new Node(3);
if (tree.isSumTree(tree.root) != 0)
System.out.println("The given tree is a SumTree");
else
System.out.println("The given tree is not a SumTree");
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to check if
# Binary tree is sum tree or not
# A binary tree node has data,
# left child and right child
class node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
def isLeaf(node):
if(node == None):
return 0
if(node.left == None and node.right == None):
return 1
return 0
# A utility function to get the sum
# of values in tree with root as root
def sum(root):
if(root == None):
return 0
return (sum(root.left) +
root.data +
sum(root.right))
# returns 1 if SumTree property holds
# for the given tree
def isSumTree(node):
# If node is None or
# it's a leaf node then return true
if(node == None or isLeaf(node)):
return 1
if(isSumTree(node.left) and isSumTree(node.right)):
# Get the sum of nodes in left subtree
if(node.left == None):
ls = 0
elif(isLeaf(node.left)):
ls = node.left.data
else:
ls = 2 * (node.left.data)
# Get the sum of nodes in right subtree
if(node.right == None):
rs = 0
elif(isLeaf(node.right)):
rs = node.right.data
else:
rs = 2 * (node.right.data)
# If root's data is equal to sum of nodes
# in left and right subtrees then return 1
# else return 0
return(node.data == ls + rs)
return 0
# Driver code
if __name__ == '__main__':
root = node(26)
root.left = node(10)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(6)
root.right.right = node(3)
if(isSumTree(root)):
print("The given tree is a SumTree ")
else:
print("The given tree is not a SumTree ")
# This code is contributed by kirtishsurangalikar
C#
// C# program to check if Binary tree
// is sum tree or not
using System;
// A binary tree node has data, left
// child and right child
public class Node
{
public int data;
public Node left, right, nextRight;
public Node(int d)
{
data = d;
left = right = nextRight = null;
}
}
public class BinaryTree{
public static Node root;
// Utility function to check if
// the given node is leaf or not
public int isLeaf(Node node)
{
if (node == null)
return 0;
if (node.left == null &&
node.right == null)
return 1;
return 0;
}
// Returns 1 if SumTree property holds
// for the given tree
public int isSumTree(Node node)
{
// For sum of nodes in left subtree
int ls;
// For sum of nodes in right subtree
int rs;
// If node is NULL or it's a leaf
// node then return true
if (node == null || isLeaf(node) == 1)
return 1;
if (isSumTree(node.left) != 0 &&
isSumTree(node.right) != 0)
{
// Get the sum of nodes in left subtree
if (node.left == null)
ls = 0;
else if (isLeaf(node.left) != 0)
ls = node.left.data;
else
ls = 2 * (node.left.data);
// Get the sum of nodes in right subtree
if (node.right == null)
rs = 0;
else if (isLeaf(node.right) != 0)
rs = node.right.data;
else
rs = 2 * (node.right.data);
// If root's data is equal to sum of
// nodes in left and right subtrees
// then return 1 else return 0
if ((node.data == rs + ls))
return 1;
else
return 0;
}
return 0;
}
// Driver code
static public void Main()
{
BinaryTree tree = new BinaryTree();
BinaryTree.root = new Node(26);
BinaryTree.root.left = new Node(10);
BinaryTree.root.right = new Node(3);
BinaryTree.root.left.left = new Node(4);
BinaryTree.root.left.right = new Node(6);
BinaryTree.root.right.right = new Node(3);
if (tree.isSumTree(BinaryTree.root) != 0)
{
Console.WriteLine("The given tree is a SumTree");
}
else
{
Console.WriteLine("The given tree is " +
"not a SumTree");
}
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program to check
// if Binary tree is sum tree or not
class Node
{
constructor(item) {
this.data = item;
this.left = null;
this.right = null;
this.nextRight = null;
}
}
let root;
/* Utility function to check if the given node is leaf or not */
function isLeaf(node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
return 0;
}
/* returns 1 if SumTree property holds for the given
tree */
function isSumTree(node)
{
let ls; // for sum of nodes in left subtree
let rs; // for sum of nodes in right subtree
/* If node is NULL or it's a leaf node then
return true */
if (node == null || isLeaf(node) == 1)
return 1;
if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0)
{
// Get the sum of nodes in left subtree
if (node.left == null)
ls = 0;
else if (isLeaf(node.left) != 0)
ls = node.left.data;
else
ls = 2 * (node.left.data);
// Get the sum of nodes in right subtree
if (node.right == null)
rs = 0;
else if (isLeaf(node.right) != 0)
rs = node.right.data;
else
rs = 2 * (node.right.data);
/* If root's data is equal to sum of nodes in left
and right subtrees then return 1 else return 0*/
if ((node.data == rs + ls))
return 1;
else
return 0;
}
return 0;
}
root = new Node(26);
root.left = new Node(10);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(6);
root.right.right = new Node(3);
if (isSumTree(root) != 0)
document.write("The given tree is a SumTree");
else
document.write("The given tree is not a SumTree");
</script>
Producción:
The given tree is a SumTree
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Método 3
- Similar al recorrido posterior al pedido, encuentre iterativamente la suma en cada paso
- Devuelve izquierda + derecha + datos actuales si izquierda + derecha es igual a los datos del Node actual
- De lo contrario, devuelve -1
C++
// C++ program to check if Binary tree
// is sum tree or not
#include<bits/stdc++.h>
using namespace std;
/* A binary tree node has data,
left child and right child */
struct node
{
int data;
node* left;
node* right;
};
/* Utility function to check if
the given node is leaf or not */
int isLeaf(node *node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
return 0;
}
/* returns data if SumTree property holds for the given
tree else return -1*/
int isSumTree(node* node)
{
if(node == NULL)
return 0;
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
ls = isSumTree(node->left);
if(ls == -1) // To stop for further traversal of tree if found not sumTree
return -1;
rs = isSumTree(node->right);
if(rs == -1) // To stop for further traversal of tree if found not sumTree
return -1;
if(isLeaf(node) || ls + rs == node->data)
return ls + rs + node->data;
else
return -1;
}
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
node* newNode(int data)
{
node* node1 = new node();
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return(node1);
}
/* Driver code */
int main()
{
node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
int total = isSumTree(root);
if(total != -1 && total == 2*(root->data))
cout<<"Tree is a Sum Tree";
else
cout<<"Given Tree is not sum Tree";
return 0;
}
// This code is contributed by Mugunthan
C++14
// C++ program to check if Binary tree
// is sum tree or not
#include<bits/stdc++.h>
using namespace std;
/* A binary tree node has data,
left child and right child */
struct node
{
int data;
node* left;
node* right;
};
/* Utility function to check if
the given node is leaf or not */
int isLeaf(node *node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
return 0;
}
/* returns data if SumTree property holds for the given
tree else return -1*/
int isSumTree(node* node)
{
if(node == NULL)
return 0;
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
ls = isSumTree(node->left);
if(ls == -1) // To stop for further traversal of tree if found not sumTree
return -1;
rs = isSumTree(node->right);
if(rs == -1) // To stop for further traversal of tree if found not sumTree
return -1;
if(isLeaf(node) || ls + rs == node->data)
return ls + rs + node->data;
else
return -1;
}
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
node* newNode(int data)
{
node* node1 = new node();
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return(node1);
}
/* Driver code */
int main()
{
node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
int total = isSumTree(root);
if(total != -1 && total == 2*(root->data))
cout<<"Sum Tree";
else
cout<<"No sum Tree";
return 0;
}
// This code is contributed by Mugunthan
Java
// Java program to check if Binary tree
// is sum tree or not
import java.util.*;
class GFG
{
/* A binary tree node has data,
left child and right child */
static class Node {
int data;
Node left, right;
}
/* Utility function to check if
the given node is leaf or not */
static int isLeaf(Node node)
{
if(node == null)
return 0;
if(node.left == null && node.right == null)
return 1;
return 0;
}
/* returns data if SumTree property holds for the given
tree else return -1*/
static int isSumTree(Node node)
{
if(node == null)
return 0;
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
ls = isSumTree(node.left);
if(ls == -1) // To stop for further traversal of tree if found not sumTree
return -1;
rs = isSumTree(node.right);
if(rs == -1) // To stop for further traversal of tree if found not sumTree
return -1;
if(isLeaf(node)==1 || ls + rs == node.data)
return ls + rs + node.data;
else
return -1;
}
/* Helper function that allocates a new node
with the given data and null left and right
pointers.
*/
static Node newNode(int data)
{
Node node1 = new Node();
node1.data = data;
node1.left = null;
node1.right = null;
return(node1);
}
public static void main(String args[])
{
Node root = newNode(26);
root.left = newNode(10);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(3);
int total = isSumTree(root);
if(total != -1 && total == 2*(root.data))
System.out.print("Tree is a Sum Tree");
else
System.out.print("Given Tree is not sum Tree");
}
}
// This code is contributed by jana_sayantan.
Python3
# Python3 program to check if
# Binary tree is sum tree or not
# A binary tree node has data,
# left child and right child
class node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
def isLeaf(node):
if(node == None):
return 0
if(node.left == None and node.right == None):
return 1
return 0
# returns data if SumTree property holds for the given
# tree else return -1
def isSumTree(node):
if(node == None):
return 0
ls = isSumTree(node.left)
if(ls == -1): #To stop for further traversal of tree if found not sumTree
return -1
rs = isSumTree(node.right)
if(rs == -1): #To stop for further traversal of tree if found not sumTree
return -1
if(isLeaf(node) or ls + rs == node.data):
return ls + rs + node.data
else:
return -1
# Driver code
if __name__ == '__main__':
root = node(26)
root.left = node(10)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(6)
root.right.right = node(3)
if(isSumTree(root)):
print("The given tree is a SumTree ")
else:
print("The given tree is not a SumTree ")
# This code is contributed by Mugunthan
C#
// C# program to check if Binary tree
// is sum tree or not
using System;
class Program {
/* A binary tree node has data,
left child and right child */
public class Node {
public int data;
public Node left, right;
}
/* Utility function to check if
the given node is leaf or not */
static int isLeaf(Node node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
return 0;
}
/* returns data if SumTree property holds for the given
tree else return -1*/
static int isSumTree(Node node)
{
if (node == null)
return 0;
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
ls = isSumTree(node.left);
if (ls == -1) // To stop for further traversal of
// tree if found not sumTree
return -1;
rs = isSumTree(node.right);
if (rs == -1) // To stop for further traversal of
// tree if found not sumTree
return -1;
if (isLeaf(node) == 1 || ls + rs == node.data)
return ls + rs + node.data;
else
return -1;
}
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
static Node newNode(int data)
{
Node node1 = new Node();
node1.data = data;
node1.left = null;
node1.right = null;
return (node1);
}
/* Driver code */
static void Main(string[] args)
{
Node root = newNode(26);
root.left = newNode(10);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(3);
int total = isSumTree(root);
if (total != -1 && total == 2 * (root.data))
Console.WriteLine("Tree is a Sum Tree");
else
Console.WriteLine("Given Tree is not sum Tree");
}
}
// This code is contributed by Tapesh(tapeshdua420)
Javascript
<script>
// JavaScript program to check if
// Binary tree is sum tree or not
// A binary tree node has data,
// left child and right child
class node{
constructor(x){
this.data = x
this.left = null
this.right = null
}
}
function isLeaf(node)
{
if(node == null)
return 0
if(node.left == null && node.right == null)
return 1
return 0
}
// returns data if SumTree property holds for the given
// tree else return -1
function isSumTree(node){
if(node == null)
return 0
let ls = isSumTree(node.left)
if(ls == -1) // To stop for further traversal of tree if found not sumTree
return -1
let rs = isSumTree(node.right)
if(rs == -1) // To stop for further traversal of tree if found not sumTree
return -1
if(isLeaf(node) || ls + rs == node.data)
return ls + rs + node.data
else
return -1
}
// Driver code
let root = new node(26)
root.left = new node(10)
root.right = new node(3)
root.left.left = new node(4)
root.left.right = new node(6)
root.right.right = new node(3)
if(isSumTree(root))
document.write("The given tree is a SumTree ")
else
document.write("The given tree is not a SumTree ")
// This code is contributed by shinjanpatra
</script>
Complejidad Temporal: O(n), ya que cada elemento se recorre una sola vez
Espacio auxiliar: O(n), debido al espacio de pila recursivo
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA