Basic Tree Questions

1.size()--------------------

Given a binary tree, count the number of nodes in the tree.
int size(struct node* node) { }

2.maxDepth()/ height()---------------both iterative and recursive ways
Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node
int maxDepth(struct node* node) {
http://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/
http://www.geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/

Modified:
http://www.geeksforgeeks.org/find-height-of-a-special-binary-tree-whose-leaf-nodes-are-connected/

3.CountLeaf()----------
Write a C Program to count leaf nodes in a binary tree.
A node is a leaf node if both left and right child nodes of it are NULL.

4.IsBTHeightBalanced()

5.Get level of a node in a binary tree

Solutions:
1.Size of a Binary Tree

int size(struct tree* root)

{

  if (root==NULL)

    return 0;

  else

    return(size(root->left) + 1 + size(root->right));

}

2.Max Depth or Height
 i)Recursive
int maxDepth(struct node* node) {
if (node==NULL) {
return(0);
}
else {
// compute the depth of each subtree
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
// use the larger one
if (lDepth > rDepth) return(lDepth+1);
else return(rDepth+1);
}
}
http://algorithms.tutorialhorizon.com/find-the-maximum-depth-or-height-of-a-binary-tree/
ii)Iterative
http://www.leetcode.com/2010/04/maximum-height-of-binary-tree.html

3.Min Value & Max Value

Concept: Given a non-empty binary search tree, return the minimum data value found in that tree. Note that the entire tree does not need to be searched. int minValue(struct node* node) {

struct node* current = node;

while (current->left != NULL {

current = current->left;   }   return(current->data); } 4.Counting Leaf Nodes unsigned int getLeafCount(struct node* node)  { if(node == NULL) return 0;  if(node->left == NULL && node->right==NULL)  return 1;  else  return getLeafCount(node->left)+getLeafCount(node->right); } 5.Binary Tree is height balanced or not An empty tree is height-balanced. A non-empty binary tree T is balanced if: 1) Left subtree of T is balanced 2) Right subtree of T is balanced 3) The difference between heights of left subtree and right subtree is not more than 1.  bool isBalanced(struct node *root) {    int lh;    int rh;     if(root == NULL)     return 1;    lh = height(root->left);    rh = height(root->right);    if( abs(lh-rh) <= 1 &&        isBalanced(root->left) &&        isBalanced(root->right))      return 1;    return 0; } 6.Get Level of a node in a binary tree: int getLevel(struct node* root, int n, int level) { if(root == NULL) return 0; if(root->data == n) return level; return getLevel(root->left, n, level+1) | getLevel(root->right, n, level+1); } 7.Get the Height of a Node in a Binary Tree http://algorithms.tutorialhorizon.com/get-the-height-of-a-node-in-a-binary-tree/ 8.Diameter of a Binary Tree[BT] http://www.geeksforgeeks.org/diameter-of-a-binary-tree/ 9.Maximum Width of a Binary Tree http://www.geeksforgeeks.org/maximum-width-of-a-binary-tree/ 10.Number of possible BSTs with n nodes http://www.geeksforgeeks.org/g-fact-18/ Strategy:  For the key values 1...numKeys, how many structurally unique  binary search trees are possible that store those keys.  Strategy: consider that each value could be the root.  Recursively find the size of the left and right subtrees. Code: int countTrees(int numKeys) {   if (numKeys <=1) {     return(1);   }   else {     // there will be one value at the root, with whatever remains     // on the left and right each forming their own subtrees.     // Iterate through all the values that could be the root...     int sum = 0;     int left, right, root;     for (root=1; root<=numKeys; root++) {       left = countTrees(root - 1);       right = countTrees(numKeys - root);       // number of possible trees with this root == left*right       sum += left*right;     }     return(sum);   } } 11.Delete a tree Write a C program to Delete a Tree.  Concept:To delete a tree we must traverse all the nodes of the tree and delete them one by one.So we should use Postorder, because before deleting the parent node we should delete its children nodes first Code: void deleteTree(struct tree*& root) {     if (root == NULL) return;     deleteTree(root->left);     deleteTree(root->right);     printf("\n Deleting node: %d", root->data);     free(root);     return NULL; }  Time Complexity: O(n) Space Complexity: If we don’t consider size of stack for function calls then O(1) otherwise O(n)