Intersection of two sorted lists or 2 sorted arrays

For two sorted lists,
1, 2, 12, 15, 17, 18
1, 12, 14, 15, 16, 18, 20
intersection is bold numbers.

Solution 1 : Brute force
 An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. We have two better solutions.

Solution 2 : Take the benefit of sorting of array
It is noticeable that the two input arrays are sorted. Supposing a number number1 in array1 equals to a number number2 in array2, the numbers after number1 in array1 should be greater than the numbers before number2 in array2. Therefore, it is not necessary to compare the numbers after number1 in array1 with numbers before number2 in array2. It improves efficiency since many comparisons are eliminated.

List getIntersection(int[] a, int[] b){
    int apos = 0, bpos = 0
    List intersection
    while apos < a.length && bpos < b.length:
        if a[apos] == b[bpos]:
            intersection.add(a[apos])
            apos++, bpos++
        else:
            if a[apos] < b[bpos]:
                apos++
            else:
                bpos++
    return intersection 
}

Time Complexity is O(m + n).
Since it only requires to scan two arrays once, its time complexity is O(m+n).


Note: Using an ArrayList wastes space, instead use LinkedList.

Solution 3 - Using binary search in O(n log m) time

As we know, a binary search algorithm requires O(logm) time to find a number in an array with length m. Therefore, if we search each number of an array with length n from an array with length m, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n). Therefore, we can implement a new and better solution based on binary search in such a situation. 

For instance, the following same code is suitable when array1 is much longer than array2.

 /* === Supposing array1 is much longer than array2 === */
void getIntersectionUsingBinarySearch(int[] array1,
                     int[] array2,
                     int[] intersection)
{
    intersection.clear();
   
    int iter1 = array1[0];
    while(iter1 != array1[array1.size-1])
    {
        if(binary_search(0, array2.size, iter1))
            intersection.add(iter1);
    }
}

Time complexity : n log (m)

Thanks.

Read More

Scrabble Algorithms

If you are playing scrabble and you have n letters, what are all the possible words that you can make from these n letters?
It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler.
Below are the possible words for letters 'abc'. I have highlighted the patterns in them.
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
For n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations of each letter which is O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). The time complexity is quite high.

All possible words for n letters can be obtained by using the permutations algorithm of n letters with a very simple mod. The changes are in blue.

permutation(char[] in){
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0)
}

permuteWords(char[] in, buffer out, bool[] used, int depth){
    print out
    if depth = in.length:
        print out
        return
    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permuteWords(in, used, out, depth +1)
       
        out.length = out.length -1
        used[i] = false
}

Time complexity is the same as that of permutations O(n^n) O(n!) [update n! not n^n].
A better way is to have each word added to a list (the list would be created in permutation method and passed as parameter to permuteWords method) for extensions of the problem. 
Possible extensions to this scrabble problem are:

• Find the longest word. 
• Find the word with maximum points given a map of points to each letter.
  
• You have a dictionary, how would you use it to get the valid words? For this, I would assume that the dictionary has a function like boolean isValidWord(String s) which would indicate if a particular word is valid or not. Here is another interesting thought with the dictionary extension which requires a trie structure. I could use a dictionary, to see if I can bust out of permuting further as mostly not all permutations are going to be valid words. For example, if you have a dictionary implemented as a trie with a function boolean hasPrefix(String s) or hasPrefix(char c) and letters 'aabc' and suppose that the dictionary does not have a trieNode structure a-a, you do not have to permute further for the unused characters 'bc'. Below is the changed code that I came up with (not tested). 

Set getValidWordsPermutation(char[] in){
    Set validWords = new HashSet();
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0, validWords);
    return validWords;
}
permuteWords(char[] in, buffer out, bool[] used, int depth, Set validWords){
    // if the current prefix is not present in the dictionary, then do not permute further with the rest of the unused letters
    if !dict.hasPrefix(out): //or dict.hasPrefix(out[out.length()])
        return
   
    //if current prefix is a word, add to the set
    if dict.isValidWord(out):
        validWords.add(out)

    if depth = in.length:
        return

    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permuteWords(in, used, out, depth +1, validWords)
       
        out.length = out.length -1
        used[i] = false
}

Using the dictionary, only those trieNodes forming valid words possible from the n letters are traversed in the dictionary trie [O(|V|+|E|) time] and not all permutations [O(n^n) time]. If all permutations are valid words OR if there is no such hasPrefix(String s) function for trie, then it takes O(n^n) time - which is better than O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). 

Read More

Tries

Trie (pronounced as try even though it stands for tree and retrieval) is a prefix tree data structure. You can read more on it on topcoder and wiki.

Trie mostly has a root node as an empty string ("") and each node has 26 child pointers letters (A to Z) at least. As we add words to it, the trie grows. Here is an example of how a trie looks (from www.danvk.org) after adding a few words to it. Note that the complete words are double rounded.
It is mainly used for longest prefix (ex: IP matching) and for dictionaries <word, meaning> pairs. For dictionary it has advantages like spell-checking, other nearest words etc.
Usually, the trie node needs to have the children pointers at the least and it can have more data members as per the problem.

class trieNode {
    trieNode[26] children
    char c //
    int countPrefix // words with prefix from root to current node
    int countWord // complete words for this current node
    meaning // pointer to meanings of this node's word (dictionary)
}

At the minimum, we need the below functions. Depending upon the problem, we add more data members, change the functions.

initialize(trieNode)
addWord(trieNode, word) //called as addWord(root, word)

Efficiency for a building a trie is O(n) for n strings as we have to add all n strings to the trie. For finding a string in a trie, it takes O(l) worst case where l is the length of the string.
Let's take a problem where we want to find the "longest prefix of a given list of strings" for given percentage of strings (i.e longest prefix for 50% of given strings). We would first form the trie with the addWord(root, word) function and then use longestPrefix().
Once the trie is formed, the problem becomes quite simple (like finding the max from a list of numbers). We maintain currPath (path from root to current node i.e. current prefix) and longestPrefix (longest prefix so far). From node's countPrefix and root's countPrefix, we calculate the node's percentage. Based on these two conditions, we change longestPrefix accordingly as we traverse the whole tree by DFS. Note that we first go deep into the tree and then check for conditions as ancestor nodes within the longestPrefix have the same prefixCount (or greater but we prefer longer prefix than greater prefixCount).

 

class trieNode:
    trieNode[26] children
    char c
    int countPrefix
    int countWord

    addWord(trieNode node, string word) {
        //we are at end of the word
        if (word = ""):
            node.countWord = node.countWord +1
            return

        //do stuff with current node
        node.countPrefix = node.countPrefix + 1
       
        //go to next node 
        char first = firstChar(word)
        if (node.children[first] == null):
            node.children[first] = new trieNode()
       
        addWord(node.children[first], firstCharRemoved(word))
    }

    addWord(trieNode root, List l) {
        for string s in l:
            addWord(root, s)
    }

    string longestPrefix(trieNode root, int percent) {
        StringBuffer currPath = new StringBuffer()
        StringBuffer longestPrefix = new StringBuffer()
        dfs(root, percent, currPath, longestPrefix)
        return longestPrefix.toString()
    }

    dfs(trieNode node, int percent, StringBuffer currPath, StringBuffer longestPrefix) {
        // append node char
        currPath.append(node.c)

        // go as deep as possible as ancestors have the same prefixCount
        // as the child within the longestPrefix
        for trieNode tn in children:
             dfs(tn, percent, currPath, longestPrefix)

        if (node.countPrefix/countPrefixForRoot *100 >= percent):
            if (currPath.length() > longestPrefix.length()):
                longestPrefix.setLength(0)
                longestPrefix.append(currPath)

        // drop last node char
        currPath.deleteCharAt(currPath.length() -1)
    }

} 

Longest Prefix problem needs O(n) time to build the trie for n strings. Then it dwindles down to DFS with (O(|V| + |E|) time to find the longest prefix.

Read More

What is BST or Binary Search tree?

A binary search tree (BST) is a tree which has following property :
Every node's left sub-tree has a key less than the node's key, and every right sub-tree has a key greater than the node's key.

The major advantage of binary search trees is that the related sorting algorithms and search algorithms, such as in-order traversal, can be very efficient. This data structure is perfect for advanced interview questions. See the figure below for this tree:

From this figure we can portray the following:
6 - Root node of the binary tree
2 - Parent node of the nodes 1 & 5
2 & 8 - Children nodes of 6 and these nodes are in a level one more than the root node 6
8 - Right child node of 6
2 - Left child node of 6
1 & 6 - These node are without a child, so they are referred to as leafs or external nodes
2 & 8 - These nodes have children/child, so they are referred to as internal nodes

Depth or Hieght of this binary tree - The longest path from the root node 6 to any leaf node, for example 1 node. Therefore, the depth of this binary tree is two. In the almost balanced tree, it is nearly log n(to base 2) and nearly n in case of almost unbalanced binary tree.

Indegree of a node - The number of edges merging into a node. For example, indegree of the node 2 is one i.e. one edge merges.
Outdegree of a node - The number of edges coming out from a node. For example, outdegree of the node 2 is two i.e. two edges comes out of this root node.

Implementing BST / ADT
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree.
Here is the example is this:

 So, here root is 5, which has left node as 3, and right node as 9. Also, note that 9 has no right node and 1,4,6 are leaf nodes as they have both right and left pointers null.

Following will be class structure of BST (following c/cpp) :

struct node {
  int data;
  struct node* left;
  struct node* right;
} ;

Note: Pointer Changing Code There is a common problem with pointer intensive code: what if a function needs to change one of the pointer parameters passed to it? For example, the insert() function below may want to change the root pointer. In C and C++, one solution uses pointers-to-pointers (aka "reference parameters"). That's a fine technique, but here we will use the simpler technique that a function that wishes to change a pointer passed to it will return the new value of the pointer to the caller. The caller is responsible for using the new value. Suppose we have a change() function that may change the the root, then a call to change() will look like this... // suppose the variable "root" points to the tree root = change(root); We take the value returned by change(), and use it as the new value for root. This construct is a little awkward, but it avoids using reference parameters which confuse some C and C++ programmers, and Java does not have reference parameters at all. This allows us to focus on the recursion instead of the pointer mechanics.
BST Speciality
Basically, binary search trees are fast at insert and lookup. The next section presents the code for these two algorithms. When we search for 4 (tree above) , we know, it is less than 5, so we go left, we get 3. We know 4 is more than right, so we go to right and finally find it.

Height of Binary tree

Height of the binary tree plays special role in lookup and other time operation time complexity. For balanced binary search tree, with N nodes can locate the item in order lg(N) time (log base 2), which is equivalent to depth of BST. By balanced I mean that height of left and right part of the tree are equal:


 But for unbalanced tree like this one (see below), the time complexity for lookup is O(n), which equivalent to height of BST.

Therefore, binary search trees are good for "dictionary" problems where the code inserts and looks up information indexed by some key. The lg(N) behavior is the average case -- it's possible for a particular tree to be much slower depending on its shape. So, in any case lookup time is O (height)

Operations of BST
 Following are the operations we perform on BST

• Lookup
• Insert
• Delete

Other operations:

• Getting Maximum -This is the same concept as minimum but you move to the right.
• Finding Predecessor -
  -- Easy Case - If k's left subtree is not empty, just return the max key in its left subtree.
  -- Harder Case - Go up parent pointers until you reach one that is less than you.
• In-Order Traversal -Let R be the root node of the search tree, with substrees T_l and T_r. Recurse on T_l. Next print out R's key. Lastly, recurse on T_r.

Lookup
Here is the code for lookup

/*
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
*/
static int lookup(node* node, int target) {
// 1. Base case == empty tree
// in that case, the target is not found so return false
    if (node == NULL) {
    return(false);
    }
    else {
// 2. see if found here
    if (target == node->data)
         return(true);
    else {
// 3. otherwise recur down the correct subtree
        if (target < node->data)
             return(lookup(node->left, target));
        else return(lookup(node->right, target));
    }
  }
}

Insert 
We piggy back on search only.We took the convention that if the key value of the inserted node is equal to the one present in tree, we move to the left of the tree.

/*gets the node of tree with value initialized with data*/
node* newNode(int data) {
  node* temp = (node*) malloc(sizeof(node)); // "new" is like "malloc"
  temp->data = data;
  temp->left = NULL;
  temp->right = NULL;

  return(temp);
}

/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
    if (node == NULL) {
        return(newNode(data));
    }
    else {
    // 2. Otherwise, recur down the tree
    if (data <= node->data) 
        node->left = insert(node->left, data);
    else 
        node->right = insert(node->right, data);
    
     return(node); // return the (unchanged) node pointer
   }
}

Getting the Min and Max of BST

Getting the Predecessor of node

Getting the Successor of a node

Traversals in BST - Inorder, PreOrder and Post Order

Deleting a Node from BST 

Select and Rank

 

Read More

Program to check if two rectangle overlap or itntersect

Input - 2 Rectangles with x and y coordinates.
Output - boolean value which states if they overlap or not 

This is a one of the classic problems in graphics programming and game development. So, let's see how we can solve it.

Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. As you move down the screen, the y value increases. And, as you move right the x value increases.

Algorithm :

• Two rectangles can overlap if one rectangle has 0,1,2,4 corners inside the other rectangle. The check of above mentioned condition could result is many different combinations. Remember overlapping rectangle cannot have 3 corners inside.
  
• Other way we can say that two rectangle overlap if the region of one rectangle lies inside the other.

• The best way to find is to identify whether an overlapping area is present or not which can be known if the below mentioned all conditions are true.
  
  If we check that( B = Black rectangle, R - Red Rectangle)
  
  
• The left edge of B is to the left of right edge of R.
• The top edge of B is above the R bottom edge.
• The right edge of B is to the right of left edge of R.
• The bottom edge of B is below the R upper edge.

Then we can say that rectangles are overlapping.

Off-course, we discussed the algorithm on matching rectangles, let's now focus on where the rectangles will not intersect.

Consider the following figure:

From those pictures, we can infer that two rectangles are not intersecting each other if they have one of the four conditions:

1. Right edge of blue is closer to the left of the screen than the left edge of red 
2. Bottom edge of blue is further from the bottom of the screen than the top edge of red 
3. Top edge of blue is closer to the bottom of the screen than the bottom edge of red 
4. Left edge of blue is further from the left of the screen than the right edge of red

Consider an example: There are two rectangles as shown in diagram – Black Rectangle (B) and Red rectangle(R).

Conditions to be checked
The left edge of B is to the left of right edge of R. The selected area will be :

The top edge of B is above the R bottom edge. So the selected area will be:

The right edge of B is to the right of left edge of R. The selected area will be:

The bottom edge of B is below the R upper edge. The selected area will be:

Hence all conditions are true we can say that rectangles are overlapping.


Therefore we can see that all the conditions are valid and hence rectangle is overlapping.
 
c++ implementation

#include<iostream>
using namespace std;

struct Point
{
  float x;
  float y;
};

struct Rect
{
  Point topLeft;
  Point bottomRight;
};

bool checkOverlap(Rect rect1, Rect rect2)
{
  if (rect1.topLeft.x >= rect2.bottomRight.x 
      || rect1.bottomRight.x <= rect2.topLeft.x 
      || rect1.topLeft.y <= rect2.bottomRight.y 
      || rect1.bottomRight.y >= rect2.topLeft.y)
    return false;
    
  return true;
}

Java implementation
Here is the java implementation for the code if you want to visualize as well. The logic is only present in checkOverlap() method, rest is used to display the GUI and check.

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;



public class RectangleOverlap extends JPanel{

 int r1x1,r1x2,r2x1,r2x2 ;
 int r1y1,r1y2,r2y1,r2y2 ;
 int r1width,r2width ;
 int r1height,r2height ;

 static JButton btn = new JButton("Check");
 public RectangleOverlap(int r1x1,int r1y1,int r1x2,int r1y2,
   int r2x1,int r2y1,int r2x2,int r2y2){

  this.r1x1=r1x1;
  this.r1x2=r1x2;
  this.r1y1=r1y1;
  this.r1y2=r1y2;
  
  this.r2x1=r2x1;
  this.r2x2=r2x2;
  this.r2y1=r2y1;
  this.r2y2=r2y2;

  r1width = Math.abs(r1x1-r1x2);
  r2width = Math.abs(r2x1-r2x2);
  r1height = Math.abs(r1y1-r1y2);
  r2height = Math.abs(r2y1-r2y2);

  addActionListener();
 }



 private void addActionListener() {
  btn.addActionListener(new ActionListener(){

   public void actionPerformed(ActionEvent e) {
    checkOverlap();
   }
  });
 }

 private void checkOverlap() {
  // condition to check whether the rectangles are overlapping or not.s
  boolean isOVerlap= ((r1x2 >= r2x1) &&
    (r1y2 >= r2y1) &&
    (r1x1 <= r2x2) &&
    (r1y1 <= r2y2));

  if(isOVerlap ){
   JOptionPane.showMessageDialog(null, "OVerlap");
  }else{
   JOptionPane.showMessageDialog(null, "No OVerlap");
  }

 }



 @Override

 protected void paintComponent(Graphics g) {
  g.drawRect(r1x1,r1y1 , r1width, r1height);
  g.setColor(new Color(123,232,122));
  g.drawRect(r2x1, r2y1, r2width,r2height);

 }



 public static void main(String args[]){
  JFrame frame = new JFrame();
  frame.setSize(500,500);

  // input to check overlap condition.

  // the order followed as : enter coordinate for 1st rectangle as
  // lower limit and upper limit to rectangles          

  frame.getContentPane().add(new RectangleOverlap(20,30,120,130,10,50,160,120),
    BorderLayout.CENTER);
  frame.getContentPane().add(btn,BorderLayout.SOUTH);
  frame.addWindowListener(new WindowAdapter(){
   @Override

   public void windowClosing(WindowEvent e) {
    System.exit(0);
   }

  });

  frame.setVisible(true);

 }

}

Sources:
http://codesam.blogspot.com/2011/02/check-if-two-rectangles-intersect.html
http://tech-read.com/2009/02/06/program-to-check-rectangle-overlapping/

Read More

Sum , factorial

/*sum upto n numbers*/ 

public static int Sum(int n)
    {
      int result = 0;
      for (int i = 1; i <= n; ++i)
         result += i;
      return result;
    }

Read More

Given two sorted arrays of size m and n respectively (m >> n), how to merge them together?

Given two sorted arrays of size m and n respectively (m >> n),  how to merge them together? 
(Note: if you try to insert n numbers to the larger array to obtain O(n \log m) complexity, pay attention that you have to move elements around for insertions. Also, simply merging those two arrays is not the optimal solution here.) 

Solution

Consider A[m+1] and B[n+1] and C[m+n] (m>>n and indexing starts from 1)
Instead of merging the 2 arrays from front end, merge them in the reverse direction-considering the largest elements(A[m] and B[n]) from both the arrays and inserting it at the (m+n)th position of A and so on.

int firstArr=m;
int secondArr=n;


for(insertPosition=m+n;i>=1;i--)
{
  if(m==-1)
  { //Transfer all remaining elements from B to C;}
  else if(n==-1)
  { //Transfer all remaining elements from A to c; }
  else
  {
    if(A[firstArr]>=B[secondArr])
    C[insertPos]=A[firstArr--];
    else C[insertPos]=B[secondArr--]
  }
} 

Read More

Interview Questions on Binary Search tree

• Given a binary tree,create the copy of the tree.
• Given a binary tree, count the number of nodes in the tree.
• Given a binary tree, find the maximum depth the number of nodes along the longest path from the root node down to the farthest leaf node.
• Write a code to find the minimum and maximum value in binary search tree
• Print the BST in increasing order…to put this in different way, it simply means to print in inorder traversal
• Print the post order traversal (recursive)
• Print the paths in binary search tree from root to leaves.
• Get the mirror of Binary tree
• BST : Binary search tree with double tree
• BT: How to check whether 2 trees are same or not?
• BST: How to check whether 2 trees are BST or NOT
• BST:Return Nth Node in in-order traversal
• Construct a tree given its inorder and preorder
• Given an expression tree, calculate the expression
• Write a code to write DFS and BFS on tree.

Read More

BST : Improving search by using sentinel

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )
{
    Node *current = this->root;

    while ( current != NULL )
    {
        if (current->data < data)
        {
            current = current->left;
        }
        else if (current->data > data)
        {
            current = current->right;
        }
        else if ( current->data == data )
        {
            return true;
        }
    }

  return false;
}

You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that’s 2500 checks.

Let’s see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;

This is how the search will look like:

static Node* Leaf;

bool BinaryTree::Search (int data )
{
    Node *current = this->root;

    Leaf->data = data;

    while ( current->data != lead->data )
    {
        if (current->data < data)
        {
            current = current->left;
        }
        else
        {
            current = current->right;
        }
    }

    return (current != Leaf);
}

The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.

This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.

Read More

Nth node in inorder traversal

Problem

Here we have to return pointer to nth node in the inorder traversal

Solution

// Get the pointer to the nth inorder node in "nthnode"
void nthinorder(node *root, int n, mynode **nthnode)
{
  static whichnode;
  static found;

  if(!found)
  {
    if(root)
    {
       nthinorder(root->left, n , nthnode);
       if(++whichnode == n)
       {
          printf("\nFound %dth node\n", n);
          found = 1;
          *nthnode = root; // Store the pointer to the nth node.
        }
       nthinorder(root->right, n , nthnode);
    }
  }
}
17. Level order traversal  
18. Number of leaves
int count_leaf(node *root)
{
if(node == NULL) return 0;
if (node->left == NULL && node->right == NULL)  //it is a leaf
   return 1;
else
return (count_leaf(node->left) + count_leaf(node->right)) ;
     
    
} 

Read More

IsBST : Check whether the tree provided is BST or not

Problem
This background is used by the next two problems: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. To be a binary search tree, for every node, all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node. Consider the following four examples...

a.  5   -> TRUE

   / \

  2   7

b.  5   -> FALSE, because the 6 is not ok to the left of the 5

   / \

  6   7

c.   5  -> TRUE

    / \

   2   7

  /

1

d.   5  -> FALSE, the 6 is ok with the 2, but the 6 is not ok with the 5

    / \

   2   7

  / \

1     6

Solutions

There are couple of solution to this.

For the first two cases, the right answer can be seen just by comparing each node to the two nodes immediately below it. However, the fourth case shows how checking the BST quality may depend on nodes which are several layers apart -- the 5 and the 6 in that case.
Method 1 - Simple Recursive Solution BUT WRONG

int isBST(struct node* node)
{
  if (node == NULL)
    return 1;
     
  // false if left is > than node 
  if (node->left != NULL && node->left->data > node->data)
    return 0;
     
  // false if right is < than node 
  if (node->right != NULL && node->right->data < node->data)
    return 0;
   
  // false if, recursively, the left or right is not a BST 
  if (!isBST(node->left) || !isBST(node->right))
    return 0;
     
  // passing all that, it's a BST 
  return 1;
}

Here is the test case which shows it fails:

So, what's the correct solution then.

Method 2 - Correct Solution
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
  if (node == NULL)
    return(true);
     
  /* false if the max of the left is > than us */
  if (node->left!=NULL && maxValue(node->left) > node->data)
    return(false);
     
  /* false if the min of the right is <= than us */
  if (node->right!=NULL && minValue(node->right) < node->data)
    return(false);
   
  /* false if, recursively, the left or right is not a BST */
  if (!isBST(node->left) || !isBST(node->right))
    return(false);
     
  /* passing all that, it's a BST */
  return(true);
} 

It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree.
Min value from BST (more here):

int minValue(struct node* node) {
  struct node current = node;   // loop down to find the leftmost leaf
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}

Max value from BST:

int maxValue(struct node* node) {
  struct node current = node;   // loop down to find the leftmost leaf
  while (current->right != NULL) {
    current = current->right;
  }
  return(current->data);
}

Time complexity : O(n^2)
(As minValue and maxValue are O(n) )
Space Complexity : O(n) [for stack space, otherwise O(1)]

Method 3 - Efficient solution
 Method 2 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.

// Returns true if the given tree is a binary 
// search tree (efficient version).
int isBST2(struct node* node) {
  return(isBSTUtil(node, INT_MIN, INT_MAX));
} 
// Returns true if the given tree is a BST and its values 
// are >= min and <= max.
int isBSTUtil(struct node* node, int min, int max) {
  if (node==NULL) return(true); 
// false if this node violates the min/max constraint
  if (node->data >max || node->data < min) return(false); 
// otherwise check the subtrees recursively, 
// tightening the min or max constraint
  return   
    isBSTUtil(node->left, min, node->data -1 ) //node->data - 1 for distinct values
    && 
    isBSTUtil(node->right, node->data+1, max)  );// for distinct values
}

Time complexity : O (n)
Space Compexity : O(n) for stack space (Otherwise O(1) as we have not used any array etc)

Method 4 - Inorder traversal (with and without aux array)
You can read about inorder traversal here.
Using aux array-
Here are the steps we have to follow:

1. Do In-Order Traversal of the given tree and store the result in a temp array.
2. Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

Time Complexity: O(n)
Space Complexity - O(n)

Without using aux array
We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST. Here is the code:

bool isBST(struct node* root)
{
    static struct node *prev = NULL;
     
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;
 
        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;
 
        prev = root;
 
        return isBST(root->right);
    }
 
    return true;
}

The use of static variable can also be avoided by using reference to prev node as a parameter. Also, we are using calling isBST with right node after setting prev to root as we care about the next node of that root.

Method 5 - Iterative solution using BFS

The below code is just a modified version of the standard non-recursive Breadth First Search (BFS) of a binary tree. If you are unfamiliar with the algorithm for BFS, you can find detailed explanation here.

struct Node
{
  Node* left;
  Node* right;
  int value;
};

bool isBST(Node* root)
{
  if (root == NULL)
    return true;
    
  stack nodeStack;

  nodeStack.push(root);

  while (!nodeStack.empty())
  {
    Node* current = nodeStack.top();
    
    nodeStack.pop();
    
    if (current->left != NULL)
    {
      nodeStack.push(current->left);
      if (current->left->value > current->value)
        return false;
    }

    if (current->right != NULL)
    {
      nodeStack.push(current->right);
      if (current->right->value < current->value)
        return false;
    }
  }

  return true;
}

Anyway, for every node we check whether its children obey the rules of binary search tree. If the current node has a left child, the child's value must be less than the current node's value. On the other hand, if the current node has a right child, the right child's value must be greater than the current node's value. Therefore, a binary tree with all nodes that satisfy those rules is a binary tree. We return true when we check all nodes and none of them violates the rules. However, if there is any violation, we simply return false.

References

• http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

Read More

Count binary search trees–Given N nodes, how many structurally BST are possible?

Problem:
This is not a binary tree programming problem in the ordinary sense -- it's more of a math/combinatorics recursion problem that happens to use binary trees. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different  binary search trees are there that store those values?



Solution
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!
See references for proof and examples.
References:
http://en.wikipedia.org/wiki/Catalan_number

Method 1 - Recursion
Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14  structurally unique binary search trees that store 1, 2, 3, and 4. The base case is easy, and the recursion is short but dense. Your code should not construct any actual trees; it's just a counting problem.

N=0, count = 1 as we can have a null tree
N = 1 , count = 1, we can have only 1 tree
N =2 , count = 2, trees being

N = 3, count = 5, trees being

N = 4, count = 14, trees being:

/*
 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.
*/
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);//number of elements in left subtree
                                  //will be less than root
      right = countTrees(numKeys - root);
      // number of possible trees with this root == left*right
      sum += left*right;
    }
    return(sum);
  }
}

Another good resource on this, for those who want to see the video : https://www.youtube.com/watch?v=UfA_v0VmiDg

Read More

Check whether binary tree are same or not?

Problem

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.

Solution

11. sameTree() Solution (C/C++)
/*
 Given two trees, return true if they are
 structurally identical.
*/
int isIdentical(struct node* a, struct node* b) {
  // 1. both empty -> true
  if (a==NULL && b==NULL) return(true);   // 2. both non-empty -> compare them
  else if (a!=NULL && b!=NULL) {
    return(
      a->data == b->data &&
      isIdentical(a->left, b->left) &&
      isIdentical(a->right, b->right)
    );
  }
  // 3. one empty, one not -> false
  else return(false);
}
 
 

Read More

Double the tree such that insert new duplicate node for each node using cpp

Problem
For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.  So the tree...
    2
   / \
  1   3
is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
1
As with the previous problem, this can be accomplished without changing the root node pointer.
Solution

/*
 For each node in a binary search tree,
 create a new duplicate node, and insert
 the duplicate as the left child of the original node.
 The resulting tree should still be a binary search tree.  So the tree...
    2
   / \
  1   3
 Is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1
*/
void doubleTree(struct node* node) {
  struct node* oldLeft;
  if (node==NULL) return;
  // do the subtrees
  doubleTree(node->left);
  doubleTree(node->right);
  // duplicate this node to its left
  oldLeft = node->left;
  node->left = newNode(node->data);
  node->left->left = oldLeft;
}

Read More

Given a BST, create a mirror of it.

Problem
Change a tree so that the roles of the left and right pointers are swapped at every node. 

Example
So the tree...
       4
      / \
     2   5
    / \
   1   3
is changed to...
       4
      / \
     5   2
        / \
       3   1
The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.

Recursive solution

/*
 Change a tree so that the roles of the
 left and right pointers are swapped at every node.  So the tree...
       4
      / \
     2   5
    / \
   1   3
 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/
void mirror(struct node* node) {
  if (node==NULL) {
    return;
  }
  else {
    struct node* temp;
    // do the subtrees
    mirror(node->left);
    mirror(node->right);
    // swap the pointers in this node
    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}
 

Iterative solution
Here is the solution:

void MirrorIterative(Node * tree)
{
 if (!tree)
  return;

 Stack s;
 s.push(tree);
 while(!s.empty())
 {
  Node * current = s.pop();
  
  // Swap the children
  //
  Node * temp = current->right;
  current->right = current->left;
  current->left = temp;

  // Push the children on the stack
  //
  if (current->right)
   s.push(current->right);

  if (current->left)
   s.push(current->left);
 }
}

This is similar to level order traversal.Thanks.

Read More

Given Binary Tree and sum, give root to leaf path such that all nodes add to that sum

We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths:

 

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

Root-to-leaf paths:
   path 1: 5 4 11 7
   path 2: 5 4 11 2
   path 3: 5 8 13
   path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

Problem 1
Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.

Solution:
Subtract the node value from the sum when recurring down,  and check to see if the sum is 0 when you run out of tree.

int hasPathSum(struct node* node, int sum) {
  // return true if we run out of tree and sum==0
  if (node == NULL) {
    return(sum == 0);
  }
  else {
  // otherwise check both subtrees
    int subSum = sum - node->data;
    return(hasPathSum(node->left, subSum) ||
           hasPathSum(node->right, subSum));
  }
}

Though this solution looks good, but it can have some flaws.Consider the case :

          5
         / \
        2   1
       /    
      3

Call the above function

hasPathSum(root, 7);

will return true.

But there is no root-to-leaf path that adds to 7. That's because when node 2 is reached, it recursively checks the right child (with sum 0), which then returns true because the right child is null.
This will return true, when the recursion is at node 2, and right null leave call will return true.

Correct solution
Lets fix it: if statement should check children and return statement deduct node.data from sum

boolean hasPathSum(Node node, int sum) { 
  int subSum = sum - node.data; 
  if(node.left==null && node.right==null) { 
    return(subSum == 0); 
  } 
  else { 
    // otherwise check both subtrees 
    if ( node.left != null && hasPathSum(node.left, subSum) ) {
        return true;
    if ( node.right != null && hasPathSum(node.right, subSum) ) {
        return true;
    }
    return false;
  } 
}

You can roll the else block into one long statement if you want (lots of ands and ors), but I find this cleaner.


Problem 2

Given a binary tree, print out all of its root-to-leaf paths as defined above. This problem is a little harder than it looks, since the "path so far" needs to be communicated between the recursive calls.  

Hint: In C, C++, and Java, probably the best solution is to create a recursive helper function printPathsRecur(node, int path[], int pathLen), where the path array communicates the sequence of nodes that led up to the current call. Alternately, the problem may be solved bottom-up, with each node returning its list of paths. This strategy works quite nicely in Lisp, since it can exploit the built in list and mapping primitives.

Given a binary tree, print out all of its root-to-leaf paths, one per line.

void printPaths(struct node* node) {
  int path[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(struct 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);
  }
}
// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
  int i;
  for (i=0; i
    printf("%d ", ints[i]);
  }
  printf("\n");
}

Reference - stanford, stackoverflow
Thanks

Read More

Print binary search tree in increasing order

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/print-binary-search-tree-in-increasing-order/.

Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order. So the tree...
       4
      / \
     2   5
    / \
   1   3
Produces the output "1 2 3 4 5". This is known as an "inorder" traversal of the tree.
Hint: For each node, the strategy is: recur left, print the node data, recur right.

Here is code in c/cpp:

void printTree(struct node* node) {

/*
 Given a binary search tree, print out
 its data elements in increasing
 sorted order.
*/
void printTree(struct node* node) {
  if (node == NULL) return;   printTree(node->left);
  printf("%d ", node->data);
  printTree(node->right);
}
 

Read More

Find the minimum data value find in Binary Search tree (using cpp)

Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function. This can be solved with recursion or with a simple while loop. int minValue(struct node* node) {

/*
 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;   // loop down to find the leftmost leaf
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}
  

Read More

Compute Maximum Depth or Height of binary search tree

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. The maxDepth of the empty tree is 0, the maxDepth of the tree below is 3.

      1
   /    \
  2      3
 /   \   /    \
4   5  6   7


Recursive approach

/*
 Compute the "maxDepth" of a tree -- the number of nodes along
 the longest path from the root node down to the farthest leaf node.
*/
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);
    }
}

Iterative approach

We could apply the same in-order traversal of a BST in the binary tree. By saying “in-order” traversal I mean traversing the tree such that it reaches the leaf first (deepest). In other words, we are doing a Depth-first Search (DFS). In fact, all three kinds of tree traversal (pre-order, in-order, and post-order) are doing DFS. Therefore, we could modify any existing iterative solution of tree traversals to solve this problem.
As pre-order and in-order iterative traversals are easier to implement, your best bet is to code either one of them during an interview session. As we traverse the tree, we would keep track of the current depth and record each node’s depth, so that we know which depth we are in when we return to the node at a later time. (In pre-order or in-order traversals, it might return several levels above the current level when a node is popped off the stack).
On the other hand, post-order traversal guarantees to return exactly one level above a node that is popped off the stack. Therefore, we could devise a solution utilizing post-order traversal without modifying the existing tree structure. We keep track of the current depth and update the maximum depth as we traverse the tree.
Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner. So BFS is like level order traversal and BFS is not.

Below is the code for finding the maximum depth of a binary tree using post-order traversal, without recursion.

int maxDepthIterative(BinaryTree *root) {
  if (!root) return 0;
  stack<BinaryTree*> s;
  s.push(root);
  int maxDepth = 0;
  BinaryTree *prev = NULL;
  while (!s.empty()) {
    BinaryTree *curr = s.top();
    if (!prev || prev->left == curr || prev->right == curr) {
      if (curr->left)
        s.push(curr->left);
      else if (curr->right)
        s.push(curr->right);
    } else if (curr->left == prev) {
      if (curr->right)
        s.push(curr->right);
    } else {
      s.pop();
    }
    prev = curr;
    if (s.size() > maxDepth)
      maxDepth = s.size();
  }
  return maxDepth;
}

Thanks.

Read More

Getting the size of Binary Search Tree

This problem demonstrates simple binary tree traversal. Given a binary tree, count the number of nodes in the tree.

Here is the code in c/cpp:

/* Compute the number of nodes in a tree. */
int size(struct node* node) { 
    if (node==NULL) { 
        return(0); 
    } else { 
        return(size(node->left) + 1 + size(node->right)); 
    }
}

Read More

Create Copy of a tree (cpp)

Given a binary tree,create the copy of the tree. node *copy(node* root)

node *copy(node *root)

 node *temp;
 
 if(root==NULL)return(NULL);
  
 temp = (node *) malloc(sizeof(node));//or temp = newNode(root->data);
 temp->value = root->value;

 temp->left  = copy(root->left);
 temp->right = copy(root->right);

 return(temp);

Read More