Getting the size of Binary Search Tree

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

This problem demonstrates simple binary tree traversal. Given a binary tree, count the number of nodes in the tree.

Here is the code in c/cpp:

/\* Compute the number of nodes in a tree. \*/  
int size(struct node\* node) {   
    if (node==NULL) {   
        return(0);   
    } else {   
        return(size(node->left) + 1 + size(node->right));   
    }  
}
tree  kodeknight  size  recursion  binary-search-tree  BST 

Create Copy of a tree (cpp)

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Given a binary tree,create the copy of the tree. node *copy(node* root)
node \*copy(node \*root)  
  
 node \*temp;  
   
 if(root==NULL)return(NULL);  
    
 temp = (node \*) malloc(sizeof(node));//or temp = newNode(root->data);  
 temp->value = root->value;  
  
 temp->left  = copy(root->left);  
 temp->right = copy(root->right);  
  
 return(temp);
tree  kodeknight  binary-search-tree  BST 

AA - tree implementation in java

 Posted on March 31, 2011  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

An AA tree in computer science is a red-black tree with one additional rule. Unlike red-black trees, RED nodes on an AA tree can only be added as a right subchild. In other words, no RED node can be a left subchild. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which greatly simplifies the maintenance operations. The following code shows how to implement a AA tree in Java: [Read More]
tree  kodeknight 

Spatial indexing with Quadtrees and Hilbert Curves

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  13 minutes  |  Kinshuk Chandra

Last Thursday night at Oredev, after the sessions, was “Birds of a Feather” - a sort of mini-unconference. Anyone could write up a topic on the whiteboard; interested individuals added their names, and each group got allocated a room to chat about the topic. I joined the “Spatial Indexing” group, and we spent a fascinating hour and a half talking about spatial indexing methods, reminding me of several interesting algorithms and techniques. [Read More]
Algorithms  kodeknight 

Anagram Trees : Part 2

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

One nice thing about working at Google is that you are surrounded by very smart people. I told one of my coworkers about the anagram tree idea, and he immediately pointed out that reordering the alphabet so that the least frequently used letters come first would reduce the branching factor early in the tree, which has the effect of reducing the overall size of the tree substantially. While this seems obvious in retrospect, it’s kind of unintuitive - usually we try to _increase_ the branching factor of n-ary trees to make them shallower and require fewer operations, rather than trying to reduce it. [Read More]
tree  kodeknight  String  anagrams 

Anagram Trees

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

When it comes to finding anagrams of words, a frequent approach is to use an anagram dictionary - simply put, sort the letters in your word to provide a unique key that all anagrams of a word have in common. Another approach is to generate a letter-frequency histogram for each letter in your word. (Both these approaches are more or less equivalent, in fact.) These approaches make the problem of finding exact single-word anagrams for strings very efficient - O(1) if you use a hashtable. [Read More]
Algorithms  kodeknight  anagrams 

Secure permutations with block ciphers

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

It’s been too long since I blogged about anything much, and way too long since I posted the first Damn Cool Algorithms post, which I promised would be a series. So here’s part 2. To start, I’m assuming you know what a permutation is - basically a shuffling of a sequence of items in a particular order. A permutation of the range 1-10, for example, is {5,2,1,6,8,4,3,9,7,10}. A secure permutation is one in which an attacker, given any subset of the permutation, cannot determine the order of any other elements. [Read More]
Algorithms  kodeknight  String  cryptography 

BK-Treesal

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

I am making my own vocab software. I provided words, meanings, synonyms, search. I feel the project is partially over. So now I thought, why not provide google-like “Did you mean” option in my search. So it all starts with this, I came closer to algorithms again. :) BK-Trees BK-Trees, or Burkhard-Keller Trees are a tree-based data structure engineered for quickly finding near-matches to a string, for example, as used by a spelling checker, or when doing a ‘fuzzy’ search for a term. [Read More]
search  Algorithms  kodeknight 

Why is manhole cover circular?

 Posted on February 6, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Reasons for the shape include: A round manhole cover cannot fall through its circular opening, whereas a square manhole cover may fall in if it were inserted diagonally in the hole. (AReuleaux triangle or other curve of constant width would also serve this purpose, but round covers are much easier to manufacture. The existence of a “lip” holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice. [Read More]
kodeknight  interview 

Deleting a middle node from a single linked list when pointer to the previous node is not available

 Posted on October 22, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e Solution If we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. [Read More]
kodeknight  link list  Single Link List  CrackingTheCodingInterview