reverse a list recursively and nonrecursively

reverse(h)
{

/*

* 1->2->p ...

* 2->1->p ...

*/

if(!h && !h->next)
return

t = h->next
h->next = NULL
while(t)
{
next = t->next
t->next = h
h = t
t = next
}
}



reverse(h)
{
/*
* 1->2->3->4
* 4->3, 1->2->3
* 4->3->2, 1->2
* 4->3->2->1
*/
if(!h && !h->next)
return

first = h
next = first->next

reverse(next)

first->next->next = first
fisrt->next = 0
h = next
}

remove a given node from a list

remove(h, a)
{
if(h == 0 || a== 0)
return ;

if(h == a)
{
a = a->next
delete h
h = a
return
}

t=h
while(t->next)
{
if(t->next == a)
{
k = t->next->next
delete t->next
t->next = k
return
}

t = t->next
}

}

construct mirror of a given binary tree

mirror(a)

if(!a)
return 0

mirror(a->left)
mirror(a->right)

swap(a->left, a->right)

check if a tree is a binary search tree (BST)

isBST(a)
{
if(!a)
return true

if( a->left && minVal(a->left) > a->num)
return false

if( a->right && maxVal(a->right) < a->num)
return false

if(!isBST(a->left) && !isBST(a->right))
return false

return true

}

serialize and deserialize a binary tree

serialize(a, list)
{
static int level = 0;
if(!a)
{
list[level++] = -1;
return
}

list[level++] = a->num;

serialize(a->left, list)
serialize(a->right, list)
}

deserialize(a, list)
{
static int level = 0;

if(list[level] == -1)
{
level++
return 0
}

a = createNode()
a->num = list[level++]
a->left = deserialize(a, list)
a->right = deserialize(a, list)
}

reverse a binary tree such that the child's left points to parent

reverse(a)
{
if(!a)
return 0

if(!a->left && !a->right)
return a

l = reverse(a->left)
if(l)
l->left = a

r = reverse(a->right)
if(r)

r->left = a;

return a
}

print all root to leaf path of a binary tree

printpath(a)
{
int path[MaxLength]
printpathrec(a, path, 0)
}

printpathrec(a, path, pathlen)
{
if(!a)
{
for i 1 to pathlen
print path[i]
}

path[pathlen] = a->num

printpathrec(a->left, path, pathlen+1)
printpathrec(a->right, path, pathlen+1)
}

count unique binary trees those can be formed from n numbers

counttrees(n)
if(n <= 1)
return 1

sum = 0

for i 1 to n
{
l = counttrees(i-1)
r = counttrees(n-i)
sum += l + r
}
return sum

find least common ancestor of a binary tree

lca(a, p, q)

if(!a)
return 0

if(a == p || a == q)
return a

l = lca(a->left, p, q)
r = lca(a->right, p, q)

if(l && r)
return a

if(l)
return l

if(r)
return r

return 0

find the maximum depth of a binary tree

maxdepth(a)
if(!a)
return 0

return 1 + max(maxdepth(a->left), maxdepth(a->right)

find the size of a tree

size(a)
if(!a)
return 0

return 1+size(a->left)+size(a->right)