Vertical sum in a binary tree

Refer : http://www.geeksforgeeks.org/archives/18215

import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.Iterator;

public class VerticalSumInTree {
 public static void main(String[] args) {
  Node root = getTree();
  printVertcalSumsInTree(root);
 }

 private static Node getTree() {
  Node node4 = new Node(4);
  Node node5 = new Node(5);
  Node node6 = new Node(6);
  Node node7 = new Node(7);
  Node node2 = new Node(2, node4, node5);
  Node node3 = new Node(3, node6, node7);
  Node root = new Node(1, node2, node3);
  return root;
 }

 private static void printVertcalSumsInTree(Node root) {

  if (root == null)
   return;

  // Used for storing nodes matches to same horizontal distance
  Map<Integer, List<Node>> map = new HashMap<Integer, List<Node>>();
  calculateVerticalSum(root, map, 0);

  printVerticalSums(map);
 }

 private static void printVerticalSums(Map<Integer, List<Node>> map) {
  if (map == null) {
   System.out.println("Tree is empty");
  } else {
   Set<Integer> keys = map.keySet();

   // Sort the keys
   // convert set to list for sorting.Because collections accepts list
   // for sorting
   List<Integer> keysList = new ArrayList<Integer>(keys);
   Collections.sort(keysList);
   // For each key, get the list of values
   for (Integer key : keysList) {
    List<Node> list = map.get(key);

    // Iterate through the list elements and calculate the sum
    int sum = 0;
    Iterator<Node> it = list.iterator();
    while (it.hasNext()) {
     Node n = it.next();
     sum = sum + n.value;
    }
    System.out.println(sum);
   }
  }
 }

 private static void calculateVerticalSum(Node root,
   Map<Integer, List<Node>> map, int horizontalDistance) {

  if (root == null)
   return;

  // Add this value to the map
  List<Node> list = map.get(horizontalDistance);
  if (list == null) {
   list = new ArrayList<Node>();
  }

  list.add(root);
  map.put(horizontalDistance, list);

  // iterate for left and right trees
  calculateVerticalSum(root.left, map, horizontalDistance - 1);
  calculateVerticalSum(root.right, map, horizontalDistance + 1);
 }

 public static class Node {

  public int value;

  // member variables will be initialized to null by default.
  public Node left;
  public Node right;

  public Node(int value) {
   this.value = value;
  }

  public Node(int value, Node left, Node right) {
   this.value = value;
   this.left = left;
   this.right = right;
  }

 }
}

Construct a Binary search tree

If you are given a number N, build a binary search tree of size N with node values from 1 to N.

public class BuildTree {

 public Node getTree(int n) {
  if (n <= 0) {
   System.out
     .println("Asking for constructing a tree of size zero or negative number.");
   return null;
  }
  return buildTree(1, n);
 }

 public Node buildTree(int left, int right) {
  if (left > right)
   return null;

  int rootValue = (int) Math.floor((left + right) / 2);
  Node node = new Node(rootValue);
  node.left = buildTree(left, rootValue - 1);
  node.right = buildTree(rootValue + 1, right);
  return node;
 }

 public static class Node {

  public int value;
  // member variables will be initialized to null by default.
  public Node left;
  public Node right;

  public Node(int value) {
   this.value = value;
  }

  public Node(int value, Node left, Node right) {
   this.value = value;
   this.left = left;
   this.right = right;
  }
 }
}

Trim Binary Search Tree

Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree. So, if we get this tree as input:

and we’re given min value as 5 and max value as 13, then the resulting binary search tree should be:

We should remove all the nodes whose value is not between min and max. We can do this by performing a post-order traversal of the tree. We first process the left children, then right children, and finally the node itself. So we form the new tree bottom up, starting from the leaves towards the root. As a result while processing the node itself, both its left and right subtrees are valid trimmed binary search trees (may be NULL as well).

http://www.ardendertat.com/2012/01/17/programming-interview-questions-26-trim-binary-search-tree/

Mirror image of a tree in iterative way

Algorithm : push all nodes of a binary tree into a stack.Pop element by element from the stack and exchange left and right pointers of the popped node.

void mirror(node* root)
{
        if(root == NULL) return;
        node *temp;
        node *q[100] = {NULL};
        int i,j;
        i = j = 0;
        
        while(root)
        {
                temp = root->left;
                root->left = root->right;
                root->right = temp;
                //printf("%d %d",root->left->data,root->right->data);
                if(root->left)
                        q[i++] = root->left;
                if(root->right)
                        q[i++] = root->right;
                root = q[j++];
        }
}

Refer for complete code : http://www.ideone.com/NyAmw

Level of a node in Binary Search Tree

int find_level(BSTreeNode root, int key) {
  int depth = 0;
  BSTreeNode temp = root;
  while (temp != null) {
   if (temp.value == key)
    return depth;
   else if (temp.value < key) {
    depth++;
    temp = temp.right;
   } else {
    depth++;
    temp = temp.left;
   }
  }
  return depth;
 }

Recursive way :

int getLevelUtil(BSTreeNode node, int data, int level)
{
  if ( node == NULL )
    return 0;
 
  if ( node->data == data )
    return level;
 
  return getLevelUtil ( node->left, data, level+1) |
         getLevelUtil ( node->right, data, level+1);
}

 
/* Returns level of given data value */
int getLevel(BSTreeNode node, int data)
{
  return getLevelUtil(node,data,1);
}

Level order tree traversal

Level order tree traversal : http://www.geeksforgeeks.org/archives/2686

Level order traversal in reverse from leaves to root :
http://tech-queries.blogspot.com/2008/12/level-order-tree-traversal-in-reverse.html

Binary Search

Jon Bentley, in his book Programming Pearls reported that he assigned binary search in a course for professional pro-
grammers and found that 90% percent failed to code it correctly despite having ample time. (Bentley’s students would have been gratified to know that his own published implementation of binary search, in a chapter titled “Writing Correct Programs”, contained a bug that remained undetected for over twenty years.) Binary search can be written in many ways—recursive, iterative, different idioms for conditionals, etc. Here is an iterative implementation adapted from Bentley’s book, which includes his bug.

public class BinSearch {
  static  int search(int[] A, int K ) {
      int l = 0;
      int u = A.length-1;
      int m;
      while(l <= u){
         m = (l+u)/2 ;
          if(A[m] < K) {
              l = m + 1;
          } else if (A[m] == K) {
              return m;
          } else {
              u = m-1;
          }
      }
      return -1;
  }
}
 

    The error is in the assignment m = (l+u)/2; it can lead to overflow and should be replaced by m = l + (u-l)/2.The time complexity of binary search is given by B(n) = c + B(n/2).This solves to B(n) = O(log n), which is far superior to the O(n) approach needed when the keys are unsorted. A disadvantage of binary search is that it requires a sorted array and sorting an array takes O(n log n) time. However if there are many searches to perform, the time taken to sort is not an issue.

static int modifiedBinarySearch(int[] a, int length, int value) {
  int low = 0;
  int high = length;
  while (low < high) {
   int mid = (low + high) / 2;
   if (a[mid] < value)
    low = mid + 1;
   else
    high = mid;
  }
  if ((low < length) && (a[low] == value))
   return low;
  else
   return -1;
 }

Binary Search Tree Validity

Write a function to determine whether a given binary tree of distinct integers is a valid binary search tree.
Assume that each node contains a pointer to its left child, a pointer to its right child, and an integer, but not a pointer to its parent. 

Answer:Note that it's not enough to write a recursive function that just checks if the left and right nodes of each node
are less than and greater than the current node (and calls that recursively).You need to make sure that all the nodes of
the subtree starting at your current node are within the valid range of values allowed by the current node's ancestors.

Therefore you can solve this recursively by writing a helper function that accepts a current node, the smallest allowed
value,and the largest allowed value for that subtree.

An example of this is the following (inJava):


boolean isValid(Node root) {
       return isValidHelper(root, Integer.MIN_VALUE,
                                      Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
       if (curr.left != null) {
              if (curr.left.value < min ||
                        !isValidHelper(curr.left, min, curr.value))
                   return false;
       }
       if (curr.right != null) {
              if (curr.right.value > max ||
                        !isValidHelper(curr.right, curr.value, max))
                   return false;
       }
       return true;
}

The running time of this algorithm is O(n).


Method II :
We can check given tree is BST or not by simply doing the in order traversal. While doing inorder traversal,don't store the elements any where.Keep track of min element.If the node value is less than means it is not sorted.So we return false.

In the initial function call  isBST(node20,-256);//min value = -256

public static boolean isBST(BTreeNode root, int min) {
  if (root == null)
   return true;
  if (!isBST(root.left, min))
   return false;
  if (root.value > min) {
   min = root.value;
  } else
   return false;
  if (!isBST(root.right, min))
   return false;
  return true;
 }

Successor/Predecessor Rules in Binary Trees

http://faculty.salisbury.edu/~ealu/COSC320/Lectures/succ_pred_rules.pdf

InOrder successor : http://geeksforgeeks.org/?p=9999

InOrder Predecessor : http://shashank7s.blogspot.com/2011/03/wap-for-inorder-predecessor.html

Remove duplicate nodes in Binary Search Tree

http://effprog.blogspot.com/2011/02/duplicate-removal-in-binary-search-tree.html


http://shashank7s.blogspot.com/2011/03/write-program-to-remove-duplicates-from.html

Largest BST in Binary Tree

• Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

         Refer : http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

• Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

         Refer : http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in_22.html

Diameter of a Binary Tree

Tree Diameter :The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.The diameter of G is defined as being the maximal distance in the graph.
The diameter of a tree T is the largest of the following quantities :
* the diameter of T’s left subtree
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed

/* Function to get diameter of a binary tree */

int diameter(struct node * tree)

{

   /* base case where tree is empty */

   if (tree == 0)

     return 0;

  /* get the height of left and right sub-trees */

  int lheight = height(tree->left);

  int rheight = height(tree->right);

  /* get the diameter of left and right sub-trees */

  int ldiameter = diameter(tree->left);

  int rdiameter = diameter(tree->right);

  /* Return max of following three

   1) Diameter of left subtree

   2) Diameter of right subtree

   3) Height of left subtree + height of right subtree + 1 */

  return max(lheight + rheight + 1, max(ldiameter, rdiameter));

}

Refer :  http://geeksforgeeks.org/?p=5687