Tries

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Trie (pronounced as try even though it stands for tree and re_trie_val) is a prefix tree data structure. You can read more on it on topcoder and wiki. Trie mostly has a root node as an empty string ("") and each node has 26 child pointers letters (A to Z) at least. As we add words to it, the trie grows. Here is an example of how a trie looks (from www. [Read More]
Algorithms  kodeknight  trie  Data Structures  DS 

Some cardinals

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

A binary tree with n nodes has exactly n+1 null nodes If there are n nodes, there exist 2^n-n different trees. No. of nodes in a full binary tree is of the form 2^k - 1 Bucket size is 1, when the overlapping and collision occur at same time Because If there is only one entry possible in the bucket, when the collision occurs, [Read More]
tree  kodeknight  Data Structures  DS  Remember 

BST - Index

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

Common Operations on BST Understanding functions of BST – insert, size and traversal Deleting a node from BST Implementing a BST in C Traversals are covered seperately below. Traversal in BST: Inorder, pre order and post order traversal(recursive approach) Inorder, pre order and post order traversal(iterative approach) Level order traversal Threaded binary tree DFS and BFS on tree Given the expression tree, calculate the expression Construct a tree, given its inorder and pre-order [Read More]
tree  kodeknight  Page  Data Structures  DS  binary-search-tree  BST  DS Concepts 

Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.

 Posted on January 25, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

For Inorder And Preorder traversals inorder = g d h b e i a f j c preorder = a b d g h e i c f j Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, “a” is the root of the tree; “gdhbei” are in the left subtree; “fjc” are in the right subtree. “b” is the next root; “gdh” are in the left subtree; “ei” are in the right subtree. [Read More]
inorder  tree  kodeknight  postorder  Data Structures  DS  preorder  traversal  binary-search-tree  BST 

Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.

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

The code below prints the paranthesized form of a tree. **print_infix_exp(node * root)** { if(root) { printf("("); infix_exp(root->left); printf(root->data); infix_exp(root->right); printf(")"); } } Creating a binary tree for a postfix expression ` *node create_tree(char postfix[]) { node *temp, *st[100]; int i,k; char symbol;  for(i=k=0; (symbol = postfix[i])!=’\0’; i++) { temp = (node *) malloc(sizeof(struct node));//temp = getnode(); temp->value = symbol; temp->left = temp->right = NULL;  if(isalnum(symbol)) st[k++] = temp; [Read More]
tree  kodeknight  Data Structures  DS  expressions  binary-search-tree  BST 

First / Lowest common ancestor (LCA) of 2 node in binary tree

 Posted on January 25, 2010  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree. Case 2- What will you do if it is Binary search tree Example So for example look into below figure: So for node 4 and 14, LCA is 8. [Read More]
tree  kodeknight  least-common-ancestor  LCA  Data Structures  DS  binary-search-tree  BST  CrackingTheCodingInterview 

Pre Order traversal - Recursive and Iterative solution

 Posted on January 24, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Example Consider the tree: div class="separator” style="clear: both; text-align: center;“> To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree. Therefore, the Preorder traversal of the above tree will outputs: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 Recursive solution preorder(N \*root) { if(root) { printf("Value : %d", root->value); preorder(root->left); preorder(root->right); } } Iterative solution [Read More]
Preorder traversal  tree  kodeknight  Data Structures  DS  preorder  traversal  binary-search-tree  BST 

Circular Queue

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

A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independent, which means that you don’t have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion. In queue, we take out the value at front and put the value at rear. [Read More]
kodeknight  queue  Data Structures  DS