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