Check if a tree is balanced

Code to check if the tree is balanced:

int maxDepth(struct Tree *node)
{
if(node == NULL) return 0;

int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);

return leftDepth > rightDepth ?
leftDepth + 1 : rightDepth + 1;
}

int minDepth(struct Tree *node)
{
if(node == NULL) return 0;

int leftDepth = minDepth(node->left);
int rightDepth = minDepth(node->right);

return leftDepth < rightDepth ?
leftDepth + 1 : rightDepth + 1;
}

bool isBalanced(struct Tree *node)
{
if(maxDepth(node)-minDepth(node) <= 1)
return true;
else
return false;
}

For complete code and other tree operations refer: click here

Lowest Common Ancestor

Lowest common ancestor of a two nodes in a tree:

Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q)
{
Tree *left, *right;
if(root == NULL) return NULL;
if(root->left == p || root->left == q
|| root->right == p || root->right == q) return root;
else {
left = lowestCommonAncestor(root->left,p,q);
right = lowestCommonAncestor(root->right, p,q);
if(left && right)
return root;
else
return (left) ? left : right;
}
}

For other tree operations or complete code refer to : click here

PrintAllPaths of a BST

Code to print all path of a binary tree:

/* printing array */
void printThisPath(int path[], int n)
{
for(int i = 0; i < n; i++)
cout << (char)path[i] << " ";
cout << endl;
}

/* recursion routine to find path */
void pathFinder(struct Tree *node, int path[], int pathLength)
{
if(node == NULL) return;
path[pathLength++] = node->data;

/* Leaf node is the end of a path.
  So, let's print the path */
if(node->left == NULL && node->right == NULL)
printThisPath(path, pathLength);
else {
pathFinder(node->left, path, pathLength);
pathFinder(node->right, path, pathLength);
}
}

/*printing all paths :
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work. */

void printAllPaths(struct Tree *root)
{
int path[100];
pathFinder(root,path,0);
}

For other tree operations or complete code refer to : click here

Check if a tree is a subtree of another tree

C++ program to check if the tree is a sub tree of another tree:
bool matchTree(Tree *r1, Tree *r2)
{
/* Nothing left in the subtree */
if(r1 == NULL && r2 == NULL)
return true;
/* Big tree empty and subtree not found */
if(r1 == NULL || r2 == NULL)
return false;
/* Not matching */
if(r1->data != r2->data)
return false;
return (matchTree(r1->left, r2->left) &&
matchTree(r1->right, r2->right));
}

bool subTree(Tree *r1, Tree *r2)
{
/*Big tree empty and subtree not found */
if(r1 == NULL)
return false;
if(r1->data == r2->data)
if(matchTree(r1, r2)) return true;
return (subTree(r1->left, r2) || subTree(r1->right, r2));
}

bool isSubTree(Tree *r1, Tree *r2)
{
/* Empty tree is subtree */
if(r2 == NULL)
return true;
else
return subTree(r1, r2);
}


For other tree operations or complete code refer to : click here

Mirror a Tree

Here is the recursive algorithm to mirror or swap the nodes:

/* change a tree so that the roles of the left
and right hand pointers are swapped at every node */
void mirror(Tree *r)
{
if(r == NULL) return;

Tree *tmp;
mirror(r->left);
mirror(r->right);

/* swap pointers */
tmp = r->right;
r->right = r->left;
r->left = tmp;
}

For other tree operations or complete code refer to : click here

Breadth First Algorithm

Breadth First Algorithm OR Level wise printing of a BST:

/* Breadth first traversal using queue */
void BreadthFirstTraversal(Tree *root)
{
if (root == NULL) return;
deque <Tree *> queue;
queue.push_back(root);

while (!queue.empty()) {
Tree *p = queue.front();
cout << p->data << " ";
queue.pop_front();

if (p->left != NULL)
queue.push_back(p->left);
if (p->right != NULL)
queue.push_back(p->right);
}
cout << endl;
}

 For other tree operations or complete code refer: click here

Size of a Binary Tree

Recursion algorithm to find out the size of a binary tree:

int treeSize(struct Tree *node)
{
if(node == NULL) return 0;
else
return treeSize(node->left) + 1 + treeSize(node->right);
} 

For other tree operations and complete code refer: click here