Amazon Interview Question SDE1s
Country: India
@whateva
u don't need to go upto leaf node in case your sum from root to current is greater than or equal to K. From this node, u can return with guarantee that your aim is achieved after this subtree.
1) pass sum of root to its children
2) compare at each level wether we have got desired sum
{
i) if yes, return true from that node
ii) else check if node is leaf node
{
a) if its a leaf node & sum is not desired one return false
}
pass sum upto this node to left subtree
if left subtree return false
remove left subtree node
pass sum upto this node to right subtree
if right subtree return false
remove right subtree node
if either of subtree has return tree
return true
else
return false
Code:
bool prunTree (tree *root, int sum, int K)
{
if (!root)
return false;
if (root->key + sum >= K)
{
return true;
}
if (!root->left && !root->right && ((root->key + sum) < K))
{
return false;
}
bool l_ret = prunTree (root->left, (root->key + sum), K);
if (l_ret == false)
{
if (root->left)
free (root->left);
root->left = NULL;
}
bool r_ret = prunTree (root->right, (root->key + sum), K);
if (r_ret == false)
{
if (root->right)
free (root->right);
root->right = NULL;
}
if (l_ret == true || r_ret == true)
return true;
else
return false;
}
void pruning (tree **root, int K)
{
if (!*root)
return;
if ((*root)->key >= K)
return;
bool ret = prunTree (*root, 0, K);
if (ret == false)
{
free (*root);
*root = NULL;
}
}
@skg.mnnit: {5,3,1,2,4,9,6} can you check for this input?
ideone.com/Fy2PPk here it is not working.
Try with K=15 as well.
@aka:
thanks for pointing out.
I forgot to add null check for root in recursion :(
updated the code with changes
public void pruneNode(ref Tree root, int max)
{
if ((root.left == null) && (root.right == null))
{
if (root.val < max)
{
root = null;
}
}
else
{
pruneNode(ref root.left, max - root.val);
pruneNode(ref root.right, max - root.val);
}
}
typedef struct node{
struct node *left;
struct node *right;
int data;
}node_t;
node_t* remPathNodesLessthanSum(
node_t *root,
int sum,
int curr_sum,
int *flag) {
int lflag=0, rflag=0;
node_t *temp;
if (!root || !flag)
return NULL;
if (!root->left && !root->right) {
if ((curr_sum + root->data)< sum) {
free(root);
*flag = 1;
return NULL;
} else
return root;
}
*flag = 0;
root->left = remPathNodesLessthanSum(
root->left,
sum,
curr_sum+root->data,
flag);
if (*flag == 1)
lflag = 1;
*flag = 0;
root->right = remPathNodesLessthanSum(
root->right,
sum,
curr_sum+root->data,
flag);
if (*flag == 1)
rflag = 1;
*flag = 0;
if ((!root->left && lflag == 1) &&
(!root->right && rflag == 1)){
*flag = 1;
free(root);
root=NULL;
} else if (!root->left && lflag == 1) {
*flag = 1;
temp = root->right;
free(root);
root=temp;
} else if (!root->right && rflag == 1) {
*flag = 1;
temp = root->left;
free(root);
root=temp;
}
return root;
}
There is very short and concise solution for this.
- Do a post order traversal
- if leafnode and sum of path < k, remove node; continue traveral
public Node prune(Node root, int k) {
return prune(root, 1, k);
}
private Node prune(Node node, int sum, int k) {
if(node.right == null && node.left == null) {
if(sum < k) return null;
else return node;
}
node.left = prune(root, node.left, sum++, k);
node.right = prune(root, node.right, sum++, k);
if(node.right == null && node.left == null) {
if(sum < k) return null;
else return node;
}
return node;
}
I believe the way "sum" is being calculated in this solution is not correct. The "sum" for a path is the sum of all nodes from root to the leaf node and this will not be known until you traverse all the way to the leaf node. while a leaf node will be part of only one path and so will have only 1 sum, a non-leaf node can be a part of multiple paths with different sums and you should delete it only if the max sum is less than K.
static void Main(string[] args)
{
foreach (int data in arr)
removeNodes(rootNode, 20, null, null);
}
static int sumOfNodes = 0;
public static bool removeNodes(Node rootNode, int limit, Node parNode, string nodeType)
{
sumOfNodes += rootNode.data;
if (rootNode.leftNode == null && rootNode.rightNode == null)
{
if (limit > sumOfNodes)
{
if (nodeType.Equals("left", StringComparison.OrdinalIgnoreCase))
parNode.leftNode = null;
else
parNode.rightNode = null;
}
}
if (rootNode.leftNode != null)
removeNodes(rootNode.leftNode, limit, rootNode, "left");
if (rootNode.rightNode != null)
removeNodes(rootNode.rightNode, limit, rootNode, "right");
sumOfNodes -= rootNode.data;
return false;
}
public int removePathWithLessSum(TreeNode node, int sumRequired) {
int leftSum = 0, rightSum = 0;
if (node == null)
return 0;
if (node.getLeftNode() != null) {
leftSum = removePathWithLessSum(node.getLeftNode(), sumRequired
- node.getValue());
if ((leftSum + node.getValue()) < sumRequired)
node.setLeftNode(null);
}
if (node.getRightNode() != null) {
rightSum = removePathWithLessSum(node.getRightNode(), sumRequired
- node.getValue());
if ((rightSum + node.getValue()) < sumRequired)
node.setRightNode(null);
}
if (node.getRightNode() != null && node.getLeftNode() != null) {
return (Math.max(leftSum, rightSum) + node.getValue());
} else if (node.getRightNode() != null) {
return (rightSum + node.getValue());
} else if (node.getLeftNode() != null) {
return (leftSum + node.getValue());
} else {
if (node == this.getRootTreeNode() && node.getValue() < sumRequired) {
this.setRootTreeNode(null);
System.out.println(callCount);
return 0;
}
return node.getValue();
}
}
public void prune(int k) {
prune(root, 0, k);
}
public int prune(Node x, int sum, int k) {
if (x == null) return sum;
sum += x.key;
if (x.left == null && x.right == null) {
if (sum < k) {
x = delete(x);
}
return sum;
}
int leftSum = 0, rightSum = 0, maxSum = 0;
if (x.left != null) {
leftSum = prune(x.left, sum, k);
if (leftSum < k) {
x.left = delete(x.left);
}
}
if (x.right != null) {
rightSum = prune(x.right, sum, k);
if (rightSum < k) {
x.right = delete(x.right);
}
}
maxSum = Math.max(leftSum, rightSum);
if (maxSum < k) {
x = delete(x);
}
return maxSum;
}
public void prune(int k) {
prune(root, 0, k);
}
public int prune(Node x, int sum, int k) {
if (x == null) return sum;
sum += x.key;
if (x.left == null && x.right == null) {
if (sum < k) {
x = delete(x);
}
return sum;
}
int leftSum = 0, rightSum = 0, maxSum = 0;
if (x.left != null) {
leftSum = prune(x.left, sum, k);
if (leftSum < k) {
x.left = delete(x.left);
}
}
if (x.right != null) {
rightSum = prune(x.right, sum, k);
if (rightSum < k) {
x.right = delete(x.right);
}
}
maxSum = Math.max(leftSum, rightSum);
if (maxSum < k) {
x = delete(x);
}
return maxSum;
}
Delete a child node only if its children are removed. I think that is the key point in the question.
My code is
void delete_some_nodes(struct node* tree,int *a,int len,int sum)
{
if(tree==NULL)return;
a[len]=tree->val;
if(tree->left==NULL && tree->right==NULL)
return;
else
{
delete_some_nodes(tree->left,a,len+1,sum);
delete_some_nodes(tree->right,a,len+1,sum);
int S=0;
for(int i=0;i<=len;i++)
S+=a[i];
if( tree->left!=NULL && (S+tree->left->val) < sum )
{
struct node* p=tree->left;
if(p->left==NULL && p->right==NULL)
{
tree->left=NULL;
free(p);
p=NULL;
}
}
if( tree->right!=NULL && (S+tree->right->val) < sum )
{
struct node* p=tree->right;
if(p->right==NULL && p->left==NULL)
{
tree->right=NULL;
free(p);
p=NULL;
}
}
}
}
void delete_some_nodes_1(struct node* tree)
{
int a[10];
int len=0;
int sum=28;
delete_some_nodes(tree,a,len,sum);
if(tree->left==NULL && tree->right==NULL)
{
if(tree->val<sum)
{
free(tree);
tree=NULL;
}
}
std::vector<int> v=full_preorder(tree);
std::vector<int>::iterator it,it2;
for(it=v.begin();it!=v.end();it++)
{
std::cout<<" "<<*it;
}
if(tree==NULL)
std::cout<<"\nTree became NULL";
else
std::cout<<"\nTree not NULL";
}
// here is a simple, cleaner and shorter code
TreeNode* prune_tree(TreeNode* root, int ps, int k, TreeNode* parent, bool leftBranch, bool rightBranch)
{
if (root == NULL) return ps > k;
ps += root->val;
bool lans = prune_tree(root->left, ps, k, root, true, false);
bool rans = prune_tree(root->right, ps, k, root, false, true);
if (lans == false && rans == false {
deleteTree(root);
if (leftBranch && parent ) parent->left = NULL;
if (rightBranch && parent ) parent->right = NULL;
}
return lans | rans ;
}
int CheckPathSum(tree * p ,int sum , int target)
{
cout<<"\n "<<p->data;
if(sum+p->data >= target)
{ cout<<"\npath sum"<<sum+p->data;
cout<<"\n path valid";
return 1;
}
int New_sum = 0;
if(p->left!=NULL)
{
if(!CheckPathSum(p->left ,sum+p->data , target))
{
p->left=NULL;
delete p->left;
}
}
if(p->right != NULL)
{
if(!CheckPathSum(p->right ,sum+p->data ,target))
{
p->right = NULL;
delete p->right;
}
}
if((p->left == NULL) && (p->right == NULL))
{
//cout<<" now finding sum for this path";
New_sum = sum + p->data;
cout<<"\npath sum"<< New_sum;
cout<<"\npath not valid";
return 0;
}
}
this one wrks for me
void deletepaths(root, par=NULL, sum=0, k, isleftNode)
{
if(!root)
return;
deletepaths(root->right, root, sum + root->data, k, false);
deletepaths(root->left, root, sum + root->data, k, true);
if(!root->left && !root->right)
{
if(isleftNode)
par->left = NULL;
else
par->right = NULL;
delete root;
}
}
how do u guys change the font or maintain indentation? the answer that i put is a normal plain text with no indentation and i am sure no one would like to comment on that :(
inside 3 open curly braces & 3 close curly braces
whenever u write code, it hints also. Pay attention to that :)
Perfrom a Depth first search traversal passing in the sum from the root to the children. When you reach the leaf node, calculate the total sum of the path. If the leaf node total sum is less than K, delete it. return the total sum calculated. Each node gets a "left_sum" and "right sum" based on left and right sub-trees. If the max(left_sum, right_sum) is less than K, then delete that node as well. Following is the code in python:
- whatevva' June 04, 2013val_node = {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4, 'e' : 5, 'f' : 6, 'g': 7 } left_child = { 'a' : 'b', 'b' : 'd', 'c' : 'f' } right_child = { 'a' : 'c', 'b' : 'e', 'c' : 'g' } def DFS(node, sum_from_root, K): val = val_node[node] + sum_from_root if (node not in left_child) and (node not in right_child): print "leaf node: " + node + "\t sum: " + str(val) if val < K: print "deleting leaf node: " + node del val_node[node] return val #returning sum from leaf if node in left_child: left_sum = DFS(left_child[node], val, K) if left_sum < K : print "deleting left child reference of : " + node del left_child[node] if node in right_child: right_sum = DFS(right_child[node], val, K) if right_sum < K : print "deleting right child reference of : " + node del right_child[node] if left_sum is None: sumx = right_sum elif right_sum is None: sumx = left_sum else: sumx = max(left_sum, right_sum) if sumx < K: del val_node[node] print "deleting node: " + node return sumx ### MAIN print "ORIGINAL TREE" print val_node print left_child print right_child DFS('a', 0, 9) print "UPDATED TREE" print val_node print left_child print right_child