Tree are of various types:
BST...
Friday, January 29, 2010
BST - Index
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
Successors and ancestors
Inorder Successor in BST
Find the...
Monday, January 25, 2010
Threaded binary tree
Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.
If (rthread == 1), then it means that the right link of the node points to the inorder success.
If its equal to 0, then the right link represents...
Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.
For Inorder And Preorder traversals
inorder = g d h b e i a f j cpreorder = 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. "d" is the next root; "g" is in the left subtree; "h" is in the right subtree.
For Inorder and Postorder traversals
Scan postorder from right to left using...
Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.
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[])
{
...
First / Lowest common ancestor (LCA) of 2 node in binary tree
This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/lowest-common-ancestor-of-a-binary-tree/.
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...
Sunday, January 24, 2010
Pre Order traversal - Recursive and Iterative solution
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]",...
Monday, January 18, 2010
Find the median in a continous stream of numbers
Problem
Numbers are randomly generated and passed to a method. Write a program
to find and maintain the median value as new values are generated.
OR
You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time)
OR
Find the rolling median?
Example
0 1 2 3 4
Right FIND MEDIAN returns 2 as median
Now input is -2 -4
So Stream = 0 1 2 3 -2 -2 -4
Sorted Stream would be -4 -2 0...
Thursday, January 14, 2010
Circular Queue
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.
Algorithm for Insertion:-
Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make...
Bubble sort
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
What is Bubble Sort?
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required.
The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order)....
Stack implementation using linked list
We will be understanding the stack implementation using linked list. So, please understand the link list before proceeding.
Lets understand how we can implement the different operation using linked list.
CPP implementation
Here is how we use linked list to implement stack in cpp:
#include <iostream>
using namespace std;
struct node
{
int info;
struct node *next;
};
struct node *top;
int empty()
{
return((top == NULL)? 1:0);
}
void push(int n)
{
struct node *p;
p=new node;
if(p!=NULL)
{
...
Radix sort
What is radix sort?
Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.
This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:
1.
Sorting takes place by distributing the list of number into a bucket by
passing through the individual digits of a given number one-by-one
beginning with the least significant part. Here, the number of buckets
are a total of ten, which bare key values starting from 0 to 9.
2. After each pass, the numbers are collected...
Quick sort
Hoore cisca discovered it in 1961.
Why quicksort?
Definitely a greatest hit algorithm
Prevalent in practice
O(n log n) time "on average"
minimal extra memory needed (which gives it leverage over merge sort)
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Quicksort helps us solving this problem.
What is quick sort?
Quick Sort is a sorting...
Merge Sort
Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort.
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set.
So,...
Thursday, January 7, 2010
Fibonacci, triangular, square, cube, pentagon numbers
Fibonacci number is N, iff 5N^2 - 4 OR 5N^2+4 is a perfect square.
Triangular number are of n(n+1) / 2
eg. 1,3,6,10,15....
Square number : N^2
Cube: N...
Array of 0 and 1, put 0's at even position and 1's at odd position
you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice verse then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.
input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }
Thursday, May 15, 2008
Deleting … Approving … ...
Subscribe to:
Posts (Atom)