Dado un árbol binario, encuentre la suma de todas las hojas que quedan en él. Por ejemplo, la suma de todas las hojas que quedan debajo del árbol binario es 5+1=6.
C++
// A C++ program to find sum of all left leaves
#include <bits/stdc++.h>
using namespace std;
/* A binary tree Node has key, pointer to left and right
children */
struct Node
{
int key;
struct Node* left, *right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointer. */
Node *newNode(int k)
{
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
// A utility function to check if a given node is leaf or not
bool isLeaf(Node *node)
{
if (node == NULL)
return false;
if (node->left == NULL && node->right == NULL)
return true;
return false;
}
// This function returns sum of all left leaves in a given
// binary tree
int leftLeavesSum(Node *root)
{
// Initialize result
int res = 0;
// Update result if root is not NULL
if (root != NULL)
{
// If left of root is NULL, then add key of
// left child
if (isLeaf(root->left))
res += root->left->key;
else // Else recur for left child of root
res += leftLeavesSum(root->left);
// Recur for right child of root and update res
res += leftLeavesSum(root->right);
}
// return result
return res;
}
/* Driver program to test above functions*/
int main()
{
// Let us a construct the Binary Tree
struct Node *root = newNode(20);
root->left = newNode(9);
root->right = newNode(49);
root->right->left = newNode(23);
root->right->right = newNode(52);
root->right->right->left = newNode(50);
root->left->left = newNode(5);
root->left->right = newNode(12);
root->left->right->right = newNode(12);
cout << "Sum of left leaves is "
<< leftLeavesSum(root);
return 0;
}
// This code is contributed by Aditya kumar (adityakumar129)
C
// A C++ program to find sum of all left leaves
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/* A binary tree Node has key, pointer to left and right
children */
struct Node
{
int key;
struct Node* left, *right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointer. */
struct Node *newNode(int k)
{
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
// A utility function to check if a given node is leaf or not
bool isLeaf(struct Node *node)
{
if (node == NULL)
return false;
if (node->left == NULL && node->right == NULL)
return true;
return false;
}
// This function returns sum of all left leaves in a given
// binary tree
int leftLeavesSum(struct Node *root)
{
// Initialize result
int res = 0;
// Update result if root is not NULL
if (root != NULL)
{
// If left of root is NULL, then add key of
// left child
if (isLeaf(root->left))
res += root->left->key;
else // Else recur for left child of root
res += leftLeavesSum(root->left);
// Recur for right child of root and update res
res += leftLeavesSum(root->right);
}
// return result
return res;
}
/* Driver program to test above functions*/
int main()
{
// Let us a construct the Binary Tree
struct Node *root = newNode(20);
root->left = newNode(9);
root->right = newNode(49);
root->right->left = newNode(23);
root->right->right = newNode(52);
root->right->right->left = newNode(50);
root->left->left = newNode(5);
root->left->right = newNode(12);
root->left->right->right = newNode(12);
printf("Sum of left leaves is %d",leftLeavesSum(root));
return 0;
}
// This code is contributed by Aditya kumar (adityakumar129)
Java
// Java program to find sum of all left leaves
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
// A utility function to check if a given node is leaf or not
boolean isLeaf(Node node)
{
if (node == null)
return false;
if (node.left == null && node.right == null)
return true;
return false;
}
// This function returns sum of all left leaves in a given
// binary tree
int leftLeavesSum(Node node)
{
// Initialize result
int res = 0;
// Update result if root is not NULL
if (node != null)
{
// If left of root is NULL, then add key of
// left child
if (isLeaf(node.left))
res += node.left.data;
else // Else recur for left child of root
res += leftLeavesSum(node.left);
// Recur for right child of root and update res
res += leftLeavesSum(node.right);
}
// return result
return res;
}
// Driver program
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(9);
tree.root.right = new Node(49);
tree.root.left.right = new Node(12);
tree.root.left.left = new Node(5);
tree.root.right.left = new Node(23);
tree.root.right.right = new Node(52);
tree.root.left.right.right = new Node(12);
tree.root.right.right.left = new Node(50);
System.out.println("The sum of leaves is " +
tree.leftLeavesSum(tree.root));
}
}
// This code is contributed by Mayank Jaiswal
Python3
# Python program to find sum of all left leaves
# A Binary tree node
class Node:
# Constructor to create a new Node
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# A utility function to check if a given node is leaf or not
def isLeaf(node):
if node is None:
return False
if node.left is None and node.right is None:
return True
return False
# This function return sum of all left leaves in a
# given binary tree
def leftLeavesSum(root):
# Initialize result
res = 0
# Update result if root is not None
if root is not None:
# If left of root is None, then add key of
# left child
if isLeaf(root.left):
res += root.left.key
else:
# Else recur for left child of root
res += leftLeavesSum(root.left)
# Recur for right child of root and update res
res += leftLeavesSum(root.right)
return res
# Driver program to test above function
# Let us construct the Binary Tree shown in the above function
root = Node(20)
root.left = Node(9)
root.right = Node(49)
root.right.left = Node(23)
root.right.right = Node(52)
root.right.right.left = Node(50)
root.left.left = Node(5)
root.left.right = Node(12)
root.left.right.right = Node(12)
print ("Sum of left leaves is", leftLeavesSum(root))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
// C# program to find sum of all left leaves
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
public Node root;
// A utility function to check if a given node is leaf or not
public virtual bool isLeaf(Node node)
{
if (node == null)
{
return false;
}
if (node.left == null && node.right == null)
{
return true;
}
return false;
}
// This function returns sum of all left leaves in a given
// binary tree
public virtual int leftLeavesSum(Node node)
{
// Initialize result
int res = 0;
// Update result if root is not NULL
if (node != null)
{
// If left of root is NULL, then add key of
// left child
if (isLeaf(node.left))
{
res += node.left.data;
}
else // Else recur for left child of root
{
res += leftLeavesSum(node.left);
}
// Recur for right child of root and update res
res += leftLeavesSum(node.right);
}
// return result
return res;
}
// Driver program
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(9);
tree.root.right = new Node(49);
tree.root.left.right = new Node(12);
tree.root.left.left = new Node(5);
tree.root.right.left = new Node(23);
tree.root.right.right = new Node(52);
tree.root.left.right.right = new Node(12);
tree.root.right.right.left = new Node(50);
Console.WriteLine("The sum of leaves is " + tree.leftLeavesSum(tree.root));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find sum of all left leaves
class Node
{
constructor(k)
{
this.data = k;
this.left = null;
this.right = null;
}
}
// A utility function to check if a given node is leaf or not
function isLeaf(node)
{
if (node == null)
return false;
if (node.left == null && node.right == null)
return true;
return false;
}
// This function returns sum of all left leaves in a given
// binary tree
function leftLeavesSum(node)
{
// Initialize result
let res = 0;
// Update result if root is not NULL
if (node != null)
{
// If left of root is NULL, then add key of
// left child
if (isLeaf(node.left))
res += node.left.data;
else // Else recur for left child of root
res += leftLeavesSum(node.left);
// Recur for right child of root and update res
res += leftLeavesSum(node.right);
}
// return result
return res;
}
// Driver program
root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.left.right = new Node(12);
root.left.left = new Node(5);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.left.right.right = new Node(12);
root.right.right.left = new Node(50);
document.write("The sum of leaves is " +leftLeavesSum(root));
// This code is contributed by unknown2108
</script>
C++
// A C++ program to find sum of all left leaves
#include <bits/stdc++.h>
using namespace std;
/* A binary tree Node has key, pointer to left and right
children */
struct Node
{
int key;
struct Node* left, *right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointer. */
Node *newNode(char k)
{
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
/* Pass in a sum variable as an accumulator */
void leftLeavesSumRec(Node *root, bool isleft, int *sum)
{
if (!root) return;
// Check whether this node is a leaf node and is left.
if (!root->left && !root->right && isleft)
*sum += root->key;
// Pass 1 for left and 0 for right
leftLeavesSumRec(root->left, 1, sum);
leftLeavesSumRec(root->right, 0, sum);
}
// A wrapper over above recursive function
int leftLeavesSum(Node *root)
{
int sum = 0; //Initialize result
// use the above recursive function to evaluate sum
leftLeavesSumRec(root, 0, &sum);
return sum;
}
/* Driver program to test above functions*/
int main()
{
// Let us construct the Binary Tree shown in the
// above figure
int sum = 0;
struct Node *root = newNode(20);
root->left = newNode(9);
root->right = newNode(49);
root->right->left = newNode(23);
root->right->right = newNode(52);
root->right->right->left = newNode(50);
root->left->left = newNode(5);
root->left->right = newNode(12);
root->left->right->right = newNode(12);
cout << "Sum of left leaves is "
<< leftLeavesSum(root) << endl;
return 0;
}
Java
// Java program to find sum of all left leaves
class Node
{
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
// Passing sum as accumulator and implementing pass by reference
// of sum variable
class Sum
{
int sum = 0;
}
class BinaryTree
{
Node root;
/* Pass in a sum variable as an accumulator */
void leftLeavesSumRec(Node node, boolean isleft, Sum summ)
{
if (node == null)
return;
// Check whether this node is a leaf node and is left.
if (node.left == null && node.right == null && isleft)
summ.sum = summ.sum + node.data;
// Pass true for left and false for right
leftLeavesSumRec(node.left, true, summ);
leftLeavesSumRec(node.right, false, summ);
}
// A wrapper over above recursive function
int leftLeavesSum(Node node)
{
Sum suum = new Sum();
// use the above recursive function to evaluate sum
leftLeavesSumRec(node, false, suum);
return suum.sum;
}
// Driver program
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(9);
tree.root.right = new Node(49);
tree.root.left.right = new Node(12);
tree.root.left.left = new Node(5);
tree.root.right.left = new Node(23);
tree.root.right.right = new Node(52);
tree.root.left.right.right = new Node(12);
tree.root.right.right.left = new Node(50);
System.out.println("The sum of leaves is " +
tree.leftLeavesSum(tree.root));
}
}
// This code is contributed by Mayank Jaiswal
Python3
# Python program to find sum of all left leaves
# A binary tree node
class Node:
# A constructor to create a new Node
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def leftLeavesSumRec(root, isLeft, summ):
if root is None:
return
# Check whether this node is a leaf node and is left
if root.left is None and root.right is None and isLeft == True:
summ[0] += root.key
# Pass 1 for left and 0 for right
leftLeavesSumRec(root.left, 1, summ)
leftLeavesSumRec(root.right, 0, summ)
# A wrapper over above recursive function
def leftLeavesSum(root):
summ = [0] # initialize result
# Use the above recursive function to evaluate sum
leftLeavesSumRec(root, 0, summ)
return summ[0]
# Driver program to test above function
# Let us construct the Binary Tree shown in the
# above figure
root = Node(20);
root.left= Node(9);
root.right = Node(49);
root.right.left = Node(23);
root.right.right= Node(52);
root.right.right.left = Node(50);
root.left.left = Node(5);
root.left.right = Node(12);
root.left.right.right = Node(12);
print ("Sum of left leaves is", leftLeavesSum(root))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
// C# program to find sum of all left leaves
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
// Passing sum as accumulator and implementing pass by reference
// of sum variable
public class Sum
{
public int sum = 0;
}
public class BinaryTree
{
public Node root;
/* Pass in a sum variable as an accumulator */
public virtual void leftLeavesSumRec(Node node, bool isleft, Sum summ)
{
if (node == null)
{
return;
}
// Check whether this node is a leaf node and is left.
if (node.left == null && node.right == null && isleft)
{
summ.sum = summ.sum + node.data;
}
// Pass true for left and false for right
leftLeavesSumRec(node.left, true, summ);
leftLeavesSumRec(node.right, false, summ);
}
// A wrapper over above recursive function
public virtual int leftLeavesSum(Node node)
{
Sum suum = new Sum();
// use the above recursive function to evaluate sum
leftLeavesSumRec(node, false, suum);
return suum.sum;
}
// Driver program
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(9);
tree.root.right = new Node(49);
tree.root.left.right = new Node(12);
tree.root.left.left = new Node(5);
tree.root.right.left = new Node(23);
tree.root.right.right = new Node(52);
tree.root.left.right.right = new Node(12);
tree.root.right.right.left = new Node(50);
Console.WriteLine("The sum of leaves is " + tree.leftLeavesSum(tree.root));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript program to find sum of all left leaves
class Node {
constructor(item) {
this.data = item;
this.left = this.right = null;
}
}
// Passing sum as accumulator and implementing pass by reference
// of sum variable
class Sum {
constructor(){
this.sum = 0;
}
}
var root;
/* Pass in a sum variable as an accumulator */
function leftLeavesSumRec( node, isleft, summ) {
if (node == null)
return;
// Check whether this node is a leaf node and is left.
if (node.left == null && node.right == null && isleft)
summ.sum = summ.sum + node.data;
// Pass true for left and false for right
leftLeavesSumRec(node.left, true, summ);
leftLeavesSumRec(node.right, false, summ);
}
// A wrapper over above recursive function
function leftLeavesSum( node) {
suum = new Sum();
// use the above recursive function to evaluate sum
leftLeavesSumRec(node, false, suum);
return suum.sum;
}
// Driver program
root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.left.right = new Node(12);
root.left.left = new Node(5);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.left.right.right = new Node(12);
root.right.right.left = new Node(50);
document.write("The sum of leaves is " + leftLeavesSum(root));
// This code contributed by gauravrajput1
</script>
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
typedef struct Node str_node;
str_node* create(int item);
int sumAllLeaftLeaves(str_node* node, bool isLeft);
int main(void)
{
int d = 0;
str_node* root = create(20);
root->left = create(9);
root->right = create(49);
root->right->left = create(23);
root->right->right = create(52);
root->right->right->left = create(50);
root->left->left = create(5);
root->left->right = create(12);
root->left->right->right = create(12);
printf("\nSum of left leaves is: %d ",
sumAllLeaftLeaves(root, false));
return 0;
}
str_node* create(int item)
{
str_node* newnode = (str_node*)malloc(sizeof(str_node));
newnode->data = item;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
int sumAllLeaftLeaves(str_node* node, bool isLeft)
{
// base case:
if (node == NULL)
return 0;
// check whether this node is a leaf node and is left.
if (node->left == NULL && node->right == NULL && isLeft)
return node->data;
// recursive case
return sumAllLeaftLeaves(node->left, true)
+ sumAllLeaftLeaves(node->right, false);
}
Java
class GFG{
static class Node {
int data;
Node left;
Node right;
};
static Node str_node;
static Node create(int item)
{
Node newnode = new Node();
newnode.data = item;
newnode.left = null;
newnode.right = null;
return newnode;
}
static int sumAllLeaftLeaves(Node node, boolean isLeft)
{
// base case:
if (node == null)
return 0;
// check whether this node is a leaf node and is left.
if (node.left == null && node.right == null && isLeft)
return node.data;
// recursive case
return sumAllLeaftLeaves(node.left, true)
+ sumAllLeaftLeaves(node.right, false);
}
public static void main(String[] args)
{
int d = 0;
Node root = create(20);
root.left = create(9);
root.right = create(49);
root.right.left = create(23);
root.right.right = create(52);
root.right.right.left = create(50);
root.left.left = create(5);
root.left.right = create(12);
root.left.right.right = create(12);
System.out.printf("\nSum of left leaves is: %d ",
sumAllLeaftLeaves(root, false));
}
}
// This code is contributed by umadevi9616
C++
// C++ program to find sum of all left leaves
#include<bits/stdc++.h>
using namespace std;
// A binary tree node
class Node
{
public:
int key;
Node* left, *right;
// A constructor to create a new Node
Node(int key_)
{
key = key_;
left = NULL;
right = NULL;
}
};
// Return the sum of left leaf nodes
int sumOfLeftLeaves(Node* root)
{
if(root == NULL)
return 0;
// Using a stack_ for Depth-First
// Traversal of the tree
stack<Node*> stack_;
stack_.push(root);
// sum holds the sum of all the left leaves
int sum = 0;
while(stack_.size() > 0)
{
Node* currentNode = stack_.top();
stack_.pop();
if (currentNode->left != NULL)
{
stack_.push(currentNode->left);
// Check if currentNode's left
// child is a leaf node
if(currentNode->left->left == NULL &&
currentNode->left->right == NULL)
{
// if currentNode is a leaf,
// add its data to the sum
sum = sum + currentNode->left->key ;
}
}
if (currentNode->right != NULL)
stack_.push(currentNode->right);
}
return sum;
}
// Driver Code
int main()
{
Node *root = new Node(20);
root->left= new Node(9);
root->right = new Node(49);
root->right->left = new Node(23);
root->right->right= new Node(52);
root->right->right->left = new Node(50);
root->left->left = new Node(5);
root->left->right = new Node(12);
root->left->right->right = new Node(12);
cout << "Sum of left leaves is "
<< sumOfLeftLeaves(root) << endl;
return 0;
}
// This code is contributed by Arnab Kundu
Java
// Java program to find sum of all left leaves
import java.util.*;
class GFG
{
// A binary tree node
static class Node
{
int key;
Node left, right;
// A constructor to create a new Node
Node(int key_)
{
this.key = key_;
this.left = null;
this.right = null;
}
};
// Return the sum of left leaf nodes
static int sumOfLeftLeaves(Node root)
{
if(root == null)
return 0;
// Using a stack_ for Depth-First
// Traversal of the tree
Stack<Node> stack_ = new Stack<>();
stack_.push(root);
// sum holds the sum of all the left leaves
int sum = 0;
while(stack_.size() > 0)
{
Node currentNode = stack_.peek();
stack_.pop();
if (currentNode.left != null)
{
stack_.add(currentNode.left);
// Check if currentNode's left
// child is a leaf node
if(currentNode.left.left == null &&
currentNode.left.right == null)
{
// if currentNode is a leaf,
// add its data to the sum
sum = sum + currentNode.left.key ;
}
}
if (currentNode.right != null)
stack_.add(currentNode.right);
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
Node root = new Node(20);
root.left= new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right= new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
System.out.print("Sum of left leaves is "
+ sumOfLeftLeaves(root) +"\n");
}
}
// This code is contributed by aashish1995
Python3
# Python3 program to find sum of all left leaves
# A binary tree node
class Node:
# A constructor to create a new Node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Return the sum of left leaf nodes
def sumOfLeftLeaves(root):
if(root is None):
return
# Using a stack for Depth-First Traversal of the tree
stack = []
stack.append(root)
# sum holds the sum of all the left leaves
sum = 0
while len(stack) > 0:
currentNode = stack.pop()
if currentNode.left is not None:
stack.append(currentNode.left)
# Check if currentNode's left child is a leaf node
if currentNode.left.left is None and currentNode.left.right is None:
# if currentNode is a leaf, add its data to the sum
sum = sum + currentNode.left.data
if currentNode.right is not None:
stack.append(currentNode.right)
return sum
# Driver Code
root = Node(20);
root.left= Node(9);
root.right = Node(49);
root.right.left = Node(23);
root.right.right= Node(52);
root.right.right.left = Node(50);
root.left.left = Node(5);
root.left.right = Node(12);
root.left.right.right = Node(12);
print('Sum of left leaves is {}'.format(sumOfLeftLeaves(root)))
C#
// C# program to find sum of all left leaves
using System;
using System.Collections.Generic;
class GFG
{
// A binary tree node
public
class Node
{
public
int key;
public
Node left, right;
// A constructor to create a new Node
public
Node(int key_)
{
this.key = key_;
this.left = null;
this.right = null;
}
};
// Return the sum of left leaf nodes
static int sumOfLeftLeaves(Node root)
{
if(root == null)
return 0;
// Using a stack_ for Depth-First
// Traversal of the tree
Stack<Node> stack_ = new Stack<Node>();
stack_.Push(root);
// sum holds the sum of all the left leaves
int sum = 0;
while(stack_.Count > 0)
{
Node currentNode = stack_.Peek();
stack_.Pop();
if (currentNode.left != null)
{
stack_.Push(currentNode.left);
// Check if currentNode's left
// child is a leaf node
if(currentNode.left.left == null &&
currentNode.left.right == null)
{
// if currentNode is a leaf,
// add its data to the sum
sum = sum + currentNode.left.key ;
}
}
if (currentNode.right != null)
stack_.Push(currentNode.right);
}
return sum;
}
// Driver Code
public static void Main(String[] args)
{
Node root = new Node(20);
root.left= new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right= new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
Console.Write("Sum of left leaves is "
+ sumOfLeftLeaves(root) +"\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find sum of all left leaves
// A binary tree node
class Node
{
// A constructor to create a new Node
constructor(key_)
{
this.key = key_;
this.left = null;
this.right = null;
}
};
// Return the sum of left leaf nodes
function sumOfLeftLeaves(root)
{
if(root == null)
return 0;
// Using a stack_ for Depth-First
// Traversal of the tree
var stack_ = [];
stack_.push(root);
// sum holds the sum of all the left leaves
var sum = 0;
while(stack_.length > 0)
{
var currentNode = stack_[stack_.length-1];
stack_.pop();
if (currentNode.left != null)
{
stack_.push(currentNode.left);
// Check if currentNode's left
// child is a leaf node
if(currentNode.left.left == null &&
currentNode.left.right == null)
{
// if currentNode is a leaf,
// add its data to the sum
sum = sum + currentNode.left.key ;
}
}
if (currentNode.right != null)
stack_.push(currentNode.right);
}
return sum;
}
// Driver Code
var root = new Node(20);
root.left= new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right= new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
document.write("Sum of left leaves is "
+ sumOfLeftLeaves(root) +"<br>");
</script>
C++
// C++ program to find sum of all left leaves
#include <bits/stdc++.h>
using namespace std;
// A binary tree node
class Node {
public:
int key;
Node *left, *right;
// constructor to create a new Node
Node(int key_)
{
key = key_;
left = NULL;
right = NULL;
}
};
// Return the sum of left leaf nodes
int sumOfLeftLeaves(Node* root)
{
if (root == NULL)
return 0;
// A queue of pairs to do bfs traversal
// and keep track if the node is a left
// or right child if boolean value
// is true then it is a left child.
queue<pair<Node*, bool> > q;
q.push({ root, 0 });
int sum = 0;
// do bfs traversal
while (!q.empty()) {
Node* temp = q.front().first;
bool is_left_child =
q.front().second;
q.pop();
// if temp is a leaf node and
// left child of its parent
if (!temp->left && !temp->right &&
is_left_child)
sum = sum + temp->key;
// if it is not leaf then
// push its children nodes
// into queue
if (temp->left) {
// boolean value is true
// here because it is left
// child of its parent
q.push({ temp->left, 1 });
}
if (temp->right) {
// boolean value is false
// here because it is
// right child of its parent
q.push({ temp->right, 0 });
}
}
return sum;
}
// Driver Code
int main()
{
Node* root = new Node(20);
root->left = new Node(9);
root->right = new Node(49);
root->right->left = new Node(23);
root->right->right = new Node(52);
root->right->right->left = new Node(50);
root->left->left = new Node(5);
root->left->right = new Node(12);
root->left->right->right = new Node(12);
cout << "Sum of left leaves is "
<< sumOfLeftLeaves(root) << endl;
return 0;
}
Java
// Java program to find sum of all left leaves
import java.util.*;
class GFG
{
// A binary tree node
static class Node
{
int key;
Node left, right;
// constructor to create a new Node
Node(int key_)
{
key = key_;
left = null;
right = null;
}
};
static class pair
{
Node first;
boolean second;
public pair(Node first, boolean second)
{
this.first = first;
this.second = second;
}
}
// Return the sum of left leaf nodes
static int sumOfLeftLeaves(Node root)
{
if (root == null)
return 0;
// A queue of pairs to do bfs traversal
// and keep track if the node is a left
// or right child if boolean value
// is true then it is a left child.
Queue<pair > q = new LinkedList<>();
q.add(new pair( root, false ));
int sum = 0;
// do bfs traversal
while (!q.isEmpty())
{
Node temp = q.peek().first;
boolean is_left_child =
q.peek().second;
q.remove();
// if temp is a leaf node and
// left child of its parent
if (is_left_child)
sum = sum + temp.key;
if(temp.left != null && temp.right != null && is_left_child)
sum = sum-temp.key;
// if it is not leaf then
// push its children nodes
// into queue
if (temp.left != null)
{
// boolean value is true
// here because it is left
// child of its parent
q.add(new pair( temp.left, true));
}
if (temp.right != null)
{
// boolean value is false
// here because it is
// right child of its parent
q.add(new pair( temp.right, false));
}
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
Node root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
System.out.print("Sum of left leaves is "
+ sumOfLeftLeaves(root) +"\n");
}
}
// This code is contributed by gauravrajput1.
Python3
# Python3 program to find sum of
# all left leaves
from collections import deque
# A binary tree node
class Node:
def __init__(self, x):
self.key = x
self.left = None
self.right = None
# Return the sum of left leaf nodes
def sumOfLeftLeaves(root):
if (root == None):
return 0
# A queue of pairs to do bfs traversal
# and keep track if the node is a left
# or right child if boolean value
# is true then it is a left child.
q = deque()
q.append([root, 0])
sum = 0
# Do bfs traversal
while (len(q) > 0):
temp = q[0][0]
is_left_child = q[0][1]
q.popleft()
# If temp is a leaf node and
# left child of its parent
if (not temp.left and
not temp.right and
is_left_child):
sum = sum + temp.key
# If it is not leaf then
# push its children nodes
# into queue
if (temp.left):
# Boolean value is true
# here because it is left
# child of its parent
q.append([temp.left, 1])
if (temp.right):
# Boolean value is false
# here because it is
# right child of its parent
q.append([temp.right, 0])
return sum
# Driver Code
if __name__ == '__main__':
root = Node(20)
root.left = Node(9)
root.right = Node(49)
root.right.left = Node(23)
root.right.right = Node(52)
root.right.right.left = Node(50)
root.left.left = Node(5)
root.left.right = Node(12)
root.left.right.right = Node(12)
print("Sum of left leaves is",
sumOfLeftLeaves(root))
# This code is contributed by mohit kumar 29
C#
// C# program to find sum of all left leaves
using System;
using System.Collections.Generic;
public class GFG
{
// A binary tree node
public
class Node
{
public int key;
public
Node left,
right;
// constructor to create a new Node
public
Node(int key_)
{
key = key_;
left = null;
right = null;
}
};
public
class pair {
public
Node first;
public
bool second;
public pair(Node first, bool second)
{
this.first = first;
this.second = second;
}
}
// Return the sum of left leaf nodes
static int sumOfLeftLeaves(Node root)
{
if (root == null)
return 0;
// A queue of pairs to do bfs traversal
// and keep track if the node is a left
// or right child if bool value
// is true then it is a left child.
Queue<pair> q = new Queue<pair>();
q.Enqueue(new pair(root, false));
int sum = 0;
// do bfs traversal
while (q.Count != 0)
{
Node temp = q.Peek().first;
bool is_left_child = q.Peek().second;
q.Dequeue();
// if temp is a leaf node and
// left child of its parent
if (is_left_child)
sum = sum + temp.key;
if (temp.left != null && temp.right != null
&& is_left_child)
sum = sum - temp.key;
// if it is not leaf then
// push its children nodes
// into queue
if (temp.left != null)
{
// bool value is true
// here because it is left
// child of its parent
q.Enqueue(new pair(temp.left, true));
}
if (temp.right != null)
{
// bool value is false
// here because it is
// right child of its parent
q.Enqueue(new pair(temp.right, false));
}
}
return sum;
}
// Driver Code
public static void Main(String[] args)
{
Node root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
Console.Write("Sum of left leaves is "
+ sumOfLeftLeaves(root) + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program to find sum of all left leaves
class Node
{
constructor(key_) {
this.left = null;
this.right = null;
this.key = key_;
}
}
// Return the sum of left leaf nodes
function sumOfLeftLeaves(root)
{
if (root == null)
return 0;
// A queue of pairs to do bfs traversal
// and keep track if the node is a left
// or right child if boolean value
// is true then it is a left child.
let q = [];
q.push([root, false ]);
let sum = 0;
// do bfs traversal
while (q.length > 0)
{
let temp = q[0][0];
let is_left_child =
q[0][1];
q.shift();
// if temp is a leaf node and
// left child of its parent
if (is_left_child)
sum = sum + temp.key;
if(temp.left != null &&
temp.right != null && is_left_child)
sum = sum-temp.key;
// if it is not leaf then
// push its children nodes
// into queue
if (temp.left != null)
{
// boolean value is true
// here because it is left
// child of its parent
q.push([temp.left, true]);
}
if (temp.right != null)
{
// boolean value is false
// here because it is
// right child of its parent
q.push([temp.right, false]);
}
}
return sum;
}
let root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
document.write("Sum of left leaves is "
+ sumOfLeftLeaves(root) +"</br>");
</script>
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