Difference Between Sums of Odd and Even Levels in Binary Trees

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Question: calculate the difference between the sum of nodes at even level and sum of nodes at odd level. Solution: recursion is the easiest way to solve this problem. At each non-null node of the tree, we have three things to do. 1) Find the difference between the node’s left child with it’s children by calling the function recursively on the node’s left child. 2) Do the same thing for the node’s right child. [Read More]
kodeknight  binary-search-tree  BST 

Find common nodes from two linked lists using recursion

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

I have to write a method that returns a linked list with all the nodes that are common to two linked lists using recursion, without loops. For example, first list is 2 -> 5 -> 7 -> 10 second list is 2 -> 4 -> 8 -> 10 the list that would be returned is 2 -> 10 I am getting nowhere with this.. What I have been think of was to check each value of the first list with each value of the second list recursively but the second list would then be cut by one node everytime and I cannot compare the next value in the first list with the the second list. [Read More]
kodeknight  link list  Single Link List  intersection 

Y – shaped Linked List. Algorithm to find the node of intersection of two lists.

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Find the node of intersection of 2 lists. Example: Solution Method 1 - Taking advantage of the link list length Here is the pseudo code to find the node of intersection of 2 lists: 1) Go through L1 and get its length l1 2) Go through L2 and get its length l2 3) Now find the difference d = l1-l2 4) So d is the number of nodes that are extra in longer list. [Read More]
kodeknight  link list  Single Link List  loop  intersection 

Remove duplicates from an unsorted linked list

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Write code to remove duplicates from an unsorted linked list. FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed? **Example ** Input/Output Original linked list: 2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null After deleting duplicate node: 2 -> 3 -> 5 -> 8 -> null We have already seen deleting duplicates from the sorted list. [Read More]
kodeknight  link list  duplicate  Single Link List  CrackingTheCodingInterview  remove-duplicates 

print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order in Binary Tree

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

/\*  
Two passes with constant space  
\*/  
int printSum(Tree t, int toPrint)  
{  
    if(t == NULL)  
        return 0;  
  
    int lsum = printSum(t->left, toPrint);  
    int rsum = printSum(t->right, 0);  
  
    int sum = lsum + t->data + rsum;  
  
    if(toPrint)  
        printf("%d ", sum);  
  
    printSum(t->right, toPrint);  
  
    return sum;  
  
}  
  
  
/\*  
One pass with n space  
\*/  
int printSum2(Tree t, int a\[\], int \*pos)  
{  
    if(t == NULL)  
        return 0;  
  
    int lsum = printSum2(t->left, a, pos);  
  
    (\*pos)++;  
  
    int p = \*pos;  
  
    int rsum = printSum2(t->right,a, pos);  
  
    return a\[p\] = lsum + t->data + rsum;  
  
  
}
tree  kodeknight  recursion  binary-search-tree  BST 

Print pascal's triangle

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Pascal’s triangle is based on this formula : C(n, r) = C(n-1, r-1) + C(n-1, r) int Pascal(int n, int r) { if (r == 0) return 1; if (n == 0) return 0; return Pascal(n - 1, k - 1) + Pascal(n - 1, r); } In cpp, this recursive routine can use both memoization and recursion: public static long nCr(int n, int r){ static unsigned long table\[256\]\[256\] = {0}; if(r == 0 || n == r) { return table\[n\]\[r\] = 1; } if(r == 1) { return table\[n\]\[r\] = n; } if(r > n / 2) { return table\[n\]\[r\] = ncr(n, n - r); } return table\[n\]\[r\] = table\[n - 1\]\[r - 1\] + table\[n - 1\]\[r\]; } In java, you can use a class and maintain the array outside the function and just use the function similar to above to update that array and return the value in the end. [Read More]
memoization  kodeknight  Dynamic Programming  DP  recursion 

What does flattening list of items into tree means

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

If I had a list of lists, “flatten” would be the operation that returns a list of all the leaf elements in order, i.e., something that changes: [[a, b, c], [d, e, f], [g, h i]] Into [a, b, c, d, e, f, g, h, i] For trees, flatting is generating a list of all leaves in natural traversal order (NB: since only leaves are in the result, it doesn’t matter whether you think of this as pre-, in- or post-order traversal. [Read More]
tree  kodeknight  traversal  binary-search-tree  BST  list 

B-tree

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Introduction B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory. To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time. [Read More]
tree  kodeknight  balanced trees  b-tree