VMWare Inc Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
int getSum(Tree root)
{
if(root==null) return 0;
if( (root.left==null) && (root.right==null)) return 0;
return root.value+getSum(root.left)+getSum(root.right);
}
int getSum(Tree root)
{
if(root==null) return 0;
if( (root.left==null) && (root.right==null)) return root.data;
return root.value+getSum(root.left)+getSum(root.right);
}
if((root.left==null)&&(root.right==null))
//it should return root.data , instead of 0
public static int sumFromNodesExcludingLeaves(BNode node, int sum) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null) {
return 0;
}
sumFromNodesExcludingLeaves(node.left, sum);
sumFromNodesExcludingLeaves(node.right, sum);
sum = sum + node.value;
return sum;
} // sumFromNodesExcludingLeaves()
Using any one traverse method (pre-order, in-order, post-order) of binary tree,
sum the non-left nodes' values.
Below is my code which using pre-order.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
struct binaryTreeNode
{
binaryTreeNode* left;
binaryTreeNode* right;
int data;
};
void createBinaryTree(binaryTreeNode*& root)
{
int itmp = 0;
cin >> itmp;
if(itmp > 0)
{
if(root == NULL)
{
root = new binaryTreeNode();
}
root->data = itmp;
root->left = 0;
root->right = 0;
createBinaryTree(root->left);
createBinaryTree(root->right);
}
}
int sumBinaryTreeNodeValue(binaryTreeNode* root)
{
int sum = 0;
binaryTreeNode* top = 0;
stack<binaryTreeNode*> bstack;
bstack.push(root);
while(!bstack.empty())
{
top = bstack.top();
bstack.pop();
if(top->left || top->right)
{
sum += top->data;
}
if(top->right)
{
bstack.push(top->right);
}
if(top->left)
{
bstack.push(top->left);
}
}
return sum;
}
void destroyBinaryTree(binaryTreeNode*& root)
{
if(root)
{
if(root->left)
{
destroyBinaryTree(root->left);
}
if(root->right)
{
destroyBinaryTree(root->right);
}
delete root;
}
}
int main()
{
binaryTreeNode* root = 0;
createBinaryTree(root);
cout << sumBinaryTreeNodeValue(root) << endl;
destroyBinaryTree(root);
return 0;
}
public class Node {
int value;
Node leftChild;
Node rightChild;
}
public static int getSumExceptLeafNodes(Node currNode) {
if(currNode == null) return 0;
else if(currNode.leftChild == null && currNode.rightChild == null)
return 0;
else {
int leftTreeSum = getSumExceptLeafNodes(currNode.leftChild);
int rightTreeSum = getSumExceptLeafNodes(currNode.rightChild);
int result = currNode.value + leftTreeSum + rightTreeSum ;
return result;
}
}
System.out.println(getSumExceptLeafNodes(rootNode));
The below function solves the problem..
public static int getSumNoLeaf(BTNode root){
int sum = 0;
BTNode temp = root;
Stack<BTNode> s = new Stack<BTNode>();
s.push(root);
while(temp != null){
if(s.isEmpty())
break;
temp = s.pop();
if(temp.getLeft()!= null || temp.getRight()!=null)
sum = sum+ temp.getData();
if(temp.getLeft()!= null){
s.push(temp.getLeft());
if(temp.getRight()!= null)
s.push(temp.getRight());
}
}
return sum;
}
{
public class BinaryTreeTest {
int sum=0;
public static void main(String[] args) {
new BinaryTreeTest().run();
}
static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
// build the simple tree from chapter 11.
Node root = new Node(5);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + root.value);
insert(root, 1);
insert(root, 8);
insert(root, 6);
insert(root, 3);
insert(root, 9);
System.out.println("Traversing tree in order");
printInOrder(root);
System.out.println("Traversing tree front-to-back from location 7");
printFrontToBack(root, 7);
}
public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) {
insert(node.left, value);
} else {
System.out.println(" Inserted " + value + " to left of "
+ node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}
public void printInOrder(Node node) {
if (node != null) {
if(node.left!= null || node.right!=null){
sum+=node.value;
}
printInOrder(node.left);
System.out.println(" Traversed " + node.value);
printInOrder(node.right);
}
System.out.println("====="+sum);
}
/**
* uses in-order traversal when the origin is less than the node's value
*
* uses reverse-order traversal when the origin is greater than the node's
* order
*/
public void printFrontToBack(Node node, int camera) {
if (node == null)
return;
if (node.value > camera) {
// print in order
printFrontToBack(node.left, camera);
System.out.println(" Traversed " + node.value);
printFrontToBack(node.right, camera);
} else if (node.value < camera) {
// print reverse order
printFrontToBack(node.right, camera);
System.out.println(" Traversed " + node.value);
printFrontToBack(node.left, camera);
} else {
// order doesn't matter
printFrontToBack(node.left, camera);
printFrontToBack(node.right, camera);
}
}
}
}
- Vir Pratap Uttam May 04, 2015