Algorithms and Me: Binary Search Tree: Trick questions

Print last K elements of Binary Search Tree.

if we need those nodes in reverse sorted order? 
Traverse right node, node and then at last left node.

void print_k_nodes(Node * node, int *K){

if(node == NULL || (*K) == 0) return;

print_k_nodes(node->right, K);

printf("\n");

printf("%d", node->value);

(*K)--;

print_k_nodes(node->left, K);

}

Worst case complexity can be O(N), if BST is completely skewed towards right, else O(K) as we would be traversing only K nodes.

Replace a node with sum of nodes which are greater than the node.

Replacing node with sum of its children nodes.

We need to something with root depending on the values returned from children nodes. What traversal processes root after it has done with children? Right, it's postorder traversal. 

int replace_sum(Node *root){

if (!root) // need 

return 0; // not good idea to return 0 for not-exists node 

int left_sum =  replace_sum(root->left);

int right_sum = replace_sum(root->right);



if(left_sum + right_sum != 0){ //need differentiate whether left and right values exists or not.

root->value = left_sum + right_sum;

}

return root->value;

}

Read full article from Algorithms and Me: Binary Search Tree: Trick questions