Oracle Interview Question
Software Engineer / DevelopersCountry: United States
what does this code is simply traverse the BST in backward order and collects sum of the elements as it goes.
output example:
5
/ \
/ \
/ \
/ \
4 7
/ / \
/ / \
2 6 8
/ \
1 3
21
/ \
/ \
/ \
/ \
26 8
/ / \
/ / \
33 15 0
/ \
35 30
public static int sumTree(Tree root, int sum) {
if (root == null)
return sum;
sum = sumTree(root.right,sum);
root.value+=sum;
sum = sumTree(root.left,root.value);
return sum;
}
This solution is wrong because it also adds the node's value to the "sum of the values of all the nodes that are greater than that node". So if we have a tree where the root is 1 and it only has a right child with a value of 2, then it would change the root to 3 (when it should change it to 2) and the right child stays at 2 (when it should be 0).
Well.. Then I am just half wrong. look at the output
root = insert(root,1);
insert(root,2);
inorder(root);
System.out.println();
chSum(root);
inorder(root);
output:
C:\javatest>java Trees
Tree questions
1 ,2 ,
2 ,2 ,
Root holds 2.
then I just need to change the case where the node is a leaf
public static int chSum(TNode node){
if(node == null){
return 0;
}else if(node.left == null && node.right == null){
return 0; // return 0,since we dont have anything left
}else{
int tmp = node.value;
node.value = chSum(node.right);
return tmp + node.value + chSum(node.left);
}
}
Here is a solution that takes O(n) time:
The idea is that we recurse the tree and we go updating every node's value. We pass a parameter called greater, which stores the sum of the values that are greater than the current node (and are coming from a different part of the tree). So when we call the recursion on a left subtree, we pass to it the sum of the nodes that a greater than it (but not part of this left subtree).
Also, the recursive function returns the sum of the nodes in the tree, which we use to calculate the new values of the nodes.
public void changeValues(Node root) {
changeValues(root, 0);
}
public int changeValues(Node root, int greater) {
if(root == null)
return 0;
tmp = root.value;
int right = changeValues(root.right, greater);
root.value = right + greater;
int left = changeValues(root.left, root.value + tmp);
return left + tmp + right;
}
Perfect, small change put if right+greater > tmp then root.value=right+greater to avoid setting 0 as the node value to right most leave node. modified code as follows
public int changeValues(Node root, int greater) {
if(root == null)
return 0;
tmp = root.value;
int right = changeValues(root.right, greater);
if((right + greater) > tmp) {
root.value = right + greater;
}
int left = changeValues(root.left, root.value + tmp);
return left + tmp + right;
}
Since we are not allowed to create global or static variable, we can create hashmap(dictionary) datastructure, to maintain the key-value pair with key as nodevalue and value as sum of values of node greater than the node and while recurssive call, we will keep on sending this hashmap as an argument and using this hashmap, we will keep on updating the value.
Please let me know if this is right approach.
// C program to find sum of all paths from root to leaves
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left, *right;
};
// function to allocate new node with given data
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
int sumOfRightsUtil(struct node* root, int inSum) {
if (root == NULL)
return 0;
int rightSum = sumOfRightsUtil(root->right, inSum);
int leftSum = sumOfRightsUtil(root->left, inSum + rightSum + root->data);
int returnSum = leftSum + rightSum + root->data;
root->data = root->data + rightSum + inSum;
return returnSum;
}
void printInorder(struct node* root) {
if (NULL != root) {
printInorder(root->left);
printf("%d, ", root->data);
printInorder(root->right);
}
}
void sumOfRights(struct node* root) {
int sum = sumOfRightsUtil(root, 0);
}
// Returns sum of all root to leaf paths. The first parameter is root
// of current subtree, the second parameter is value of the number formed
// by nodes from root to this node
// Driver function to test the above functions
int main()
{
struct node *root = newNode(6);
root->left = newNode(3);
root->right = newNode(5);
root->right->right= newNode(7);
root->left->left = newNode(2);
root->left->right = newNode(5);
root->right->right = newNode(4);
root->left->right->left = newNode(7);
root->left->right->right = newNode(4);
printInorder(root);
sumOfRights(root);
printf("\n");
printInorder(root);
return 0;
}
When we do reverse inorder traverse of BST, that is right--root--left, the nodes visited before current node are those having greater value. By keeping a record of the sum of all nodes visited, we can easily fix the problem.
Following is C code:
void replaceWithSumOfAllGreater(TreeNode* root, int* pSum)
{
if(root == NULL) return;
replaceWithSumOfAllGreater(root->right, pSum);
int tmp = *pSum + root->val;
root->val = *pSum;
*pSum = tmp;
replaceWithSumOfAllGreater(root->left, pSum);
}
void replaceWithSumOfAllGreater(TreeNode* root)
{
int sum = 0;
replaceWithSumOfAllGreater(root, &sum);
}
if(root != null) {
updateNodeValue(root, 0);
}
void updateNodeValue(Node n, int val) {
n.data = n.data + val;
if(n.left != null) {
updateNodeValue(n.left, n.data);
}
if(n.right != null) {
updateNodeValue(n.right, n.data);
}
}
if(root != null) {
updateNodeValue(root);
}
int updateNodeValue(Node n) {
if(n.right != null) {
n.data = n.data + updateNodeValue(n.right);
}
if(n.left != null) {
n.left.data = n.left.data + n.data;
int temp1 = 0, temp2 = 0;
if(n.left.right != null && n.left.right.right == null && n.data > n.left.right.data) {
temp1 = n.left.right.data + n.data;
}
temp2 = updateNodeValue(n.left);
if(temp1 != 0) {
n.left.right.data = temp1;
}
return temp2;
}
return n.data;
}
I came up with this above solution. it worked with different examples. Please try and let me know if it has any issues.
void reverseorder(tNode *n, int& sum) {
if (n == NULL)
return;
reverseorder(n->right, sum);
int tmp = sum;
sum += n->data;
n->data = tmp;
reverseorder(n->left, sum);
}
Its bascially reverse inorder traversal. But we also need to clarify, in case there are duplicate nodes, whether to consider those while adding up .. This code does not care of duplicate nodes
:) Inorder traversal gives the tree in sorted order: L(D) R ... if we reverse the calls to right and left, we can get the same in reverse sorted order ... so now ... just before printing, one can keep count of how already printed. O(n) solution. Very simple.
public static int chSum(TNode node){
if(node == null){
return 0;
}else if(node.left == null && node.right == null){
return node.value;
}else{
int tmp = node.value;
node.value = chSum(node.right);
return tmp + node.value + chSum(node.left);
}
}
- Alex February 20, 2014