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...

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.aababcacacbbbabacbcbcaccacabcbcbaFor n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations...

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....

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...

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...

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]...

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...

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...

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...

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...

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!...

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,...

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   3is changed to...       2      / \     2   3    /   /   1   3  /1As with the previous problem, this can be accomplished without changing the...

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,...

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   ...

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   3Produces the output "1 2 3 4 5". This is known as an...

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; ...

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...

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