*****Program to count leaf nodes in a binary tree*****
getLeafCount(node)
1) If node is NULL then return 0.
2) Else If left and right child nodes are NULL return 1.
3) Else recursively calculate leaf count of the tree using below formula.
Leaf count of a tree = Leaf count of left subtree +
Leaf count of right subtree
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
****Convert a Binary Tree into its Mirror Tree*****
1) Call Mirror for left-subtree i.e., Mirror(left-subtree)
2) Call Mirror for right-subtree i.e., Mirror(right-subtree)
3) Swap left and right subtrees.
temp = left-subtree
left-subtree = right-subtree
right-subtree = temp
check:
For two trees ‘a’ and ‘b’ to be mirror images, the following three conditions must be true:
1. Their root node’s key must be same
2. Left subtree of root of ‘a’ and right subtree root of ‘b’ are mirror.
3. Right subtree of ‘a’ and left subtree of ‘b’ are mirror.
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Find the Maximum Depth or Height of a Tree******
maxDepth()
1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Construct Tree from given Inorder and Preorder traversals*****
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
Node buildTree(char in[], char pre[], int inStrt, int inEnd)
{
if (inStrt > inEnd)
return null;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
Node tNode = new Node(pre[preIndex++]);
/* If this node has no children then return */
if (inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode.data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode.left = buildTree(in, pre, inStrt, inIndex - 1);
tNode.right = buildTree(in, pre, inIndex + 1, inEnd);
return tNode;
}
int search(char arr[], int strt, int end, char value)
{
int i;
for (i = strt; i <= end; i++)
{
if (arr[i] == value)
return i;
}
return i;
}
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
****Binary tree, print all root-to-leaf paths****
void printPaths(Node node)
{
int path[] = new int[1000];
printPathsRecur(node, path, 0);
}
/* Recursive helper function -- given a node, and an array
containing the path from the root node up to but not
including this node, print out all the root-leaf paths.*/
void printPathsRecur(Node node, int path[], int pathLen)
{
if (node == null)
return;
/* append this node to the path array */
path[pathLen] = node.data;
pathLen++;
/* it's a leaf, so print the path that led to here */
if (node.left == null && node.right == null)
printArray(path, pathLen);
else
{
/* otherwise try both subtrees */
printPathsRecur(node.left, path, pathLen);
printPathsRecur(node.right, path, pathLen);
}
}
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Print nodes at k distance from root******
void printKDistant(Node node, int k)
{
if (node == null)
return;
if (k == 0)
{
System.out.print(node.data + " ");
return;
}
else
{
printKDistant(node.left, k - 1);
printKDistant(node.right, k - 1);
}
}
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*******Ancestors of a given node in Binary Tree*******
boolean printAncestors(Node node, int target)
{
/* base cases */
if (node == null)
return false;
if (node.data == target)
return true;
/* If target is present in either left or right subtree
of this node, then print this node */
if (printAncestors(node.left, target)
|| printAncestors(node.right, target))
{
System.out.print(node.data + " ");
return true;
/* Else return false */
return false;
}
