Postorder traversal of a binary tree without recursion

void BSTree::postorder()
{
stack<Node*> st;
set<Node*> visit;
if(root.get() == NULL)
return;
st.push(root.get());

while(!st.empty())
{
Node* curr = st.top();
if(curr->left.get() != NULL && visit.find(curr->left.get()) == visit.end())
st.push(curr->left.get());
else if(curr->right.get() != NULL && visit.find(curr->right.get()) == visit.end())
st.push(curr->right.get());
else
{
cout<<curr->data<<'\t';
visit.insert(curr);
st.pop();
}
}
}

Preorder traversal of a binary tree without recursion

void BSTree::preorder()
{
bool done = false;
stack<Node*> st;
Node* curr = root.get();

while(!done)
{
if(curr != NULL)
{
cout<<curr->data<<'\t';
st.push(curr);
curr = curr->left.get();
}
else
{
if(!st.empty())
{
curr = st.top()->right.get();
st.pop();
}
else
done = true;
}

}
}

Inorder traversal of a binary tree without recursion

void BSTree::inorder()
{
bool done = false;
stack<Node*> st;
Node* curr = root.get();
while(!done)
{
if(curr != NULL)
{
st.push(curr);
curr = curr->left.get();
}
else
{
if(!st.empty())
{
curr = st.top();
cout<<curr->data<<'\t';
st.pop();
curr = curr->right.get();
}
else
done = true;
}
}
}

Adobe Question: Url Encode a string

A buffer of infinite length is given. You need to change < to < and > to >

Solution:

void encode()
{
char str[2048] = "ab<bc>nn<";
int len = strlen(str);
int count = 0;
for(int i = 0; i < len; ++i)
{
(str[i] == '<' || str[i] == '>') && (++count);
}

int newLen = len + 3*count;
str[newLen] = '\0';
for(int i = newLen-1, j = len-1; j>=0; --j)
{
if(str[j] == '<' || str[j] == '>')
{
str[i--] = ';';
str[i--] = 't';
(str[j] == '<') && (str[i--] = 'l') || (str[i--] = 'g');
str[i--] = '&';
}
else
str[i--] = str[j];
}
cout<<'\n'<<str<<"\n\n";
}

[Adobe] Find median of infinite stream of numbers

Problem: The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for arr = [1, 2, 3], the median is 1.
• For example, for arr = [1, 2], the median is (1 + 2) / 2 = 1.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void AddNum(int num) adds the integer num from the data stream to the data structure.
• double FindMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Approach: Use one max heap and one min heap in following way:

• Max heap will be containing the numbers which are less than median.
• Min heap will be containing the numbers which are greater than or equals to median.
• Difference between the size of two heaps will never be greater than 1.

The numbers in max heap should be less than numbers in min heap so if the current number is less than or equal to the top of max heap then it will go to max heap otherwise it will go to min heap. 

We just need to take care of the violation of third condition after insertion.

When we try to find the median, we can just see if max heap has more elements than min heap (case of number of elements are odd) then we can return it's top otherwise its the case of even number so we can safely return (top of max heap + top of min heap) / 2.


Implementation in C#:

public class IntMaxCompare : IComparer<int>

{

    public int Compare(int x, int y) => y.CompareTo(x);

}

public class MedianFinder

{

    public MedianFinder()

    {

        this.maxHeap = new PriorityQueue<int, int>(new IntMaxCompare());

        this.minHeap = new PriorityQueue<int, int>();

    }

   

    public void AddNum(int num)

    {

        if (this.maxHeap.Count == 0 || this.maxHeap.Peek() >= num)

        {

            this.maxHeap.Enqueue(num, num);

        }

        else

        {

            this.minHeap.Enqueue(num, num);

        }

        if (this.maxHeap.Count > this.minHeap.Count + 1)

        {

            int elem = this.maxHeap.Dequeue();

            this.minHeap.Enqueue(elem, elem);

        }

        else if (this.maxHeap.Count < this.minHeap.Count)

        {

            int elem = this.minHeap.Dequeue();

            this.maxHeap.Enqueue(elem, elem);

        }

    }

   

    public double FindMedian()

    {

        if (this.maxHeap.Count > this.minHeap.Count)

        {

            return (double) this.maxHeap.Peek();

        }

        return (this.maxHeap.Peek() + this.minHeap.Peek()) / 2.0;

    }

    PriorityQueue<int, int> maxHeap;

    PriorityQueue<int, int> minHeap;

}

Complexity: AddNum - O(logn), FindMedian - O(1)

Microsoft Question: Find diameter of a binary tree

Problem: The diameter or width of a tree is the number of nodes on the longest path between two leaves in the tree.

Example:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Approach: Diameter of a binary tree = MAX(height of left sub-tree + height of right sub-tree,
diameter of left sub-tree,
diameter of right sub-tree)

Implementation:

    int diameter(Node* node, int& height)
    {
        int lh = 0, rh = 0, ld = 0, rd = 0;
        if(node == NULL)
        {
            height = 0;
            return 0;
        }

        ld = diameter(node->left, lh);
        rd = diameter(node->right, rh);

        height = max(lh, rh) + 1;

        return MAX(lh + rh + 1, ld, rd);
    }

Complexity: O(n)

Find Depth of a binary tree

Problem: Given the root of a binary tree, return its depth. A binary tree's depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Input: root = [1,null,2]
Output: 2

Approach: We can use post order traversal here. The simple formula of depth is Max(Depth(left), Depth(right) + 1. Obviously, if root itself is null then the depth is 0.

Implementation in C#:

    public int MaxDepth(TreeNode root)

    {

        if (root == null)

        {

            return 0;

        }

        return Math.Max(this.MaxDepth(root.left),

                        this.MaxDepth(root.right)) + 1;

    }

Complexity: O(n)

Google Question: Find nth minimum in Binary Search Tree.

1. Without extra field in Node structure --

Do inorder traversal and count number of node visited. When count is equal to n return the node.
void BSTree::findNthElem(Node* node, int& n, int& retval)
{
if(!node && n)
retval = -1;
else if(n)
{
findNthElem(node->left, n, retval);
if(n)
{
n = n - 1;
if(n == 0)
retval = node->data;
findNthElem(node->right, n, retval);
}
}
}