Binary Tree Operations.

Code for following problems:


1. Given a binary tree, count the number of nodes in the tree.
2. 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.
3. 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.
4. Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order.
5. 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.
6. Given a binary tree, print out all of its root-to-leaf paths, one per line.
7. Change a tree so that the roles of the left and right pointers are swapped at every node.
8. 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.
9. 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? 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.
10. Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.

Code:

First Non-Repeated Character in the String.

Given a String, find the first non-repeated character in the string.


Input:
abcdeecbkbala
Output:
Input String:
abcdeecbkbala
First non-repeated char in the string: d


Code:

Fibonacci Numbers

Recursive definition:
Fn = 0 if n= 0;
= 1 if n= 1;
= F(n-1) + F(n-2) if n>=2
0 1 1 2 3 5 8 13 21 34 ...

Output:

Printing fibonacci sequence till 9:
0 1 1 2 3 5 8 13 21 
Calculating fibonacci sequence iteratively till 9: 
0 1 1 2 3 5 8 13 21 

Powering a Number in O(logn) Time.

Problem:Compute a^n, where n is a natural number.
Naive algorithm:Θ(n).
a^n = a^(n/2) * a^(n/2) if n is even;
= a^((n–1)/2) * a^((n–1)/2) * a if n is odd;


Divide-and-conquer algorithm:
T(n) = T(n/2) + Θ(1) ⇒T(n) = Θ(lgn).


Input:
15
7
Output:
15^7 = 170859375


Code:

Multiply long numbers.

Write a function to take two arbitrarily long numbers in the form of Strings and multiply them, returning another String with the product.
Input:
2839745624
8769342123
Output:
2839745624 x 8769342123 = 24902700919148119752


Code:

Kth Smallest element in Binary Search Tree in O(N) - Recursive and Iterative.

Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
Write a function that takes a binary tree as input, and have it perform In order traversal - recursive and then iterative

Output:
97 92 3 10 87 6 46
Printing inorder:
3 6 10 46 87 92 97
K value: 3
Kth Smallest Node Value: 10
Kth Node :10

Retrieving an element with a given rank from a Binary Search Tree in O(logN) time.

The given Binary Search Tree has an extra information in each of its node.
Each node of the BST contains a field called "size", which is the number of internal nodes in
the subtree rooted at node (including node itself).

Find Minimum element in sorted but rotated array

Input:
6 5 4 2 3
Output:
Elements in the array:
6 5 4 2 3
Min:2


Code:

Maximum sum submatrix of a given Matrix.

Approach:

Median of Numbers, which is distributed across N machines.

Approach (Based upon quick sort):

1. Designate one computer as the master and others as slave.
2. Let the Master choose one random number, say X from its array of numbers and ask all the other slave nodes to partition their arrays based on Pivot X.
3. Then Slave nodes report back the count of numbers less than X and count of numbers more than X (can be done in parallel).
4. The Master node then add all the numbers received less than X and more than X and checks if the median is less than or greater than X.
5. Now choose X2 based upon the partition data depending upon where the median might be ie in the left partition or the right partition.
6. Continue till we get median.

Given an Array A, calculate Array B, where B[i] contains the product of all values of Array A except A[i]

Input:
6 5 4 1 2


Output:
Printing the input Array:
6 5 4 1 2
Printing B:
1 6 30 120 120
Printing C:
40 8 2 2 1
Result Array values:
40 48 60 240 120


Code:

Find an element in a matrix, whose rows are sorted left to right and cols are sorted top to bottom

Input:
3
3
1 2 3
4 5 6
7 8 9
7
Output:
1 2 3
4 5 6
7 8 9
KEY:7
Key Search? true


Code:

Infix Order of a BinaryTree

Print a binary tree in infix order. Recursive and iterative.

Output:
These nodes are inserted into BST:
16 39 43 65 56 77 22
Printing BST inorder:
16 22 39 43 56 65 77
Printing infix order iteratively:
16 22 39 43 56 65 77

Code:

Binary search on a sorted, but rotated array.

An element in a sorted array can be found in O(log n) time via binary search. But suppose We rotate the sorted array at some pivot unknown to us beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated array in O(log n) time.

Idea:
idea: look at end of array. if the last item is smaller than the key i am searching for and key is less than the mid value, then the array is rotated. this means you need to search for items in the lower part of the array.


i.e. array = (456123) val = 5


else look at the beginning of array. if the first item is bigger than the key i am searching for and key is greater than the mid value, then the array is rotated. this means you need to search for items in the upper part of the array.


i.e. array = (67812345) val = 4


otherwise, the array is not rotated. so, you can proceed with normal binary search.


i.e. array = (12345678) val = any number




Input:
9 2 3 4 5 6 7 8


Output:
Elements in Array:
9 2 3 4 5 6 7 8
Searching for key: 3
Search result: true


Code:

Reverse Stack In Place

Reverse a stack in place.

Input:
3 4 5 6 7


Output:
Original stack:
3 -> 4 -> 5 -> 6 -> 7 -> Null
Reversed stack:
7 -> 6 -> 5 -> 4 -> 3 -> Null

Stack Sorting in place.

Sort the stack in place.

input:
5
3
5
4
1
2
output:
Sorted Stack:
5 4 3 2 1

Anagram sets from dictionary

Find all the anagram sets from given list of words.

Input:
5
cat
eat
act
tea
ate
output:
Anagram sets are:
eat tea ate
cat act