Today we look at another coding problem along the same lines as the one we have seen in the previous post and the one before.
This time we have

// Postorder   C D B F E A
// Inorder       C B D A E F
// Build tree

We use relative comparisons which has worked for us before. Let us take the example of  our elemental subtree of a root with two siblings.
   J
K  L

1) All three nodes
    Post: K L J
    InOrder: K J L
2) Only left -subtree
    Post: K J
    In: K J    // L is missing because the previous element in post order lies within inIndex < that of J
3) Only right-subtree
    Post: L J
     InL J L  // K is missing when no elements appear before J whose inIndex < that of J
4) only root
Post:     Prev root Next
In :        Prev some-others root yet-others Next
4) is not differentiable from 2)

In general, with arbitrary sub-trees  for siblings
// left-subtree missing when
Previous node in pre appears to the rightof inIndex of root in inorder
// right-subtree missing when
previous element is left subtree in post order.

the sizes of the left and right sub tree can be kept track of because we use the same predecessor technique

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    N    O
Post: H I D J K E B L  M F N O G C A
In:    H D I B J E K A  L  F M C N G O

Node Rebuild(List<Node> post, List<node> in) // All nodes in list initialized with left and right = null and set only with data
{
assert( post != null && in != null);
assert (posts.Count() == in.Count());

for(int i =  post.Count()-1; I >= 0; I--)
{
Node root = post[i];
int inIndex= Array.indexOf(in, post[i]);
if ( I > 0 && I < post.Count())
{
//todo
int inIndexPrev = Array.indexOf(in, post[I-1]);
// Ignore comments below
// Ignore : Instead of taking subtree lengths, can we detect if subtrees are null from pattern
//Ignore: int inIndexNext = Array.indexOf(in, post[I+1]);
//Ignore: if both left and right subtree is null, handle it separately,
// Ignore: if (in.Count() - 1 - inIndex > 0)
// Ignore:if (inIndexPrev < inIndex && inIndexNext > inIndex)  continue;
//otherwise keep track of right subtree length as the differences in inorder indexes

     Int parent = findParentIndex (Post, i); //parent occurs to the right of root in post with left,right set
     Int parentin = Array.indexOf(in, post[parent]); // defaults to in.Count()
     Int righttreelen = parentIn-inIndex-1;
     if (i-righttreelen-1 > 0)
          Root.left = post [i-righttreelen-1];
     Int right = i-1;
     if (right > 0)
         Root.right = post [right];

}
return post[post.Count() - 1];
}

The recursive solution online is as follows:
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd)
return null;

int rootValue = postorder[postEnd];
TreeNode root = new TreeNode(rootValue);

int k = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) {
k = i;
break;
}
}

root.left = buildTree(inorder, inStart, k - 1, postorder, postStart,
postStart + k - (inStart + 1));
// Becuase k is not the length, it it need to -(inStart+1) to get the length
root.right = buildTree(inorder, k + 1, inEnd, postorder, postStart + k- inStart, postEnd - 1);
// postStart+k-inStart = postStart+k-(inStart+1) +1

return root;
}

Today we improve the performance of the previous code sample shown to reconstruct the tree from the preorder and inorder traversals.
The key to improving performance is that we do that many steps as it takes to rebuild the tree and as cheaply as possible. while this might sound cliched, it may translate to our problem this way. Are there any redundant operations in the previous code shown ? The answer is yes, We do repeated Array.IndexOf ? How do we avoid this?
Because we deal with a tree, we know all test cases can be covered by the elementary tree with a single node and two siblings where one or more nodes can be null.
Consequently, we take node J as root with left K and Right L
we have

1) Both siblings:
Pre: JKL
In: KJL
2) Right sibling only:
Pre: JL
In: JL
3) Left Sibling only
Pre: JK
In: KJ

When the siblings are trees
4) No leftchild:
Pre: J some-other-node
In: J  intermediary-nodes some-other-node
5) No right child:
Pre:  J some-other-node
In: some-other-node  intermediary-nodes J


Therefore we can use relative positions and indexes instead of absolute indexes to optimize the solution. We make the following observations:
The next element to a node in preorder has an index lesser than its own in the in order and this implies the next element is a left child.
The next element to a node has an immediate next index in the inorder as well then the next element is a right child
The next element to a node has an index greater than its own + 1, then it has no right child.
The previous element to a node in pre order occurs as the next element in the in order means that the node has no left child

Node Rebuild(List<Node> pre, List<node> in) // All nodes in list initialized with left and right = NULL and set only with data
{
assert( pre != NULL && in != null);
assert (pre.Count() == in.Count());

for(int i = 0; i < pre.Length; i++)
{
Node root = pre[i];
int inIndex= Array.indexOf(in, pre[i]);
if (i+1 < pre.Length && inIndex+1<in.Length)
{
//todo:
//set root.left
bool left = true;
for (int j =inIndex; j< in.Count(); j++)
     if (in[j] == pre[i+1])
       left = false;
if(left != false)
  root.left = pre[i+1];
//set root.right
bool right= true;
for (int j =inIndex; j>= 0 j--)
     if (in[j] == pre[i+1])
       right = false;
if(right != false){
   Node target = in[inIndex-1];
   for(int j =i+1; j<pre.Count();j++)
    if (pre[j] == target)
        root.right = pre[j];
}
}
}

return pre[0];
}

Some can claim that yesterday's approach was development oriented and today's approach is test-oriented and there may be some truth in that there are entrenched mindsets along those lines but the reality is that today's approach is leaned on for real world data.

Today we look at using the Binary tree traversals to reconstruct the tree. We mentioned in yesterday's post that the preorder traversal and the inorder traversal can be used to determine the length of the left and right subtree of any node at the same time. Let us take a look at the solution now.

// Preorder A B C D E F
// Inorder   C B D A E F
// Build tree

Node BuildTree(char[] Preorder, char[] InOrder, int index = 0)
{
 Node root = new Node();
 root.data = PreOrder[index];
 root.left = null;
 root.right = null;

 int inIndex = Array,indexOf(InOrder, Preorder[index]);

 if ( index+1 < Preorder.Length &&
       IsLeftSubtree(Preorder[index+1], inOrder, inIndex) == true)
       root.left = BuildTree(Preorder, InOrder, index + 1);

 if ( inIndex+1 < InOrder.Length &&
       isPredecessor(InOrder[inIndex+1], Preorder, index) == false)
       root.right = BuildTree(Preorder, InOrder, Array.IndexOf(PreOrder, InOrder[inIndex + 1]));

 return root;
}

bool is Predecessor(char c, char[] Preorder, int index)
{
return Array.IndexOf(Preorder, c) < index;
}

bool isLeftSubtree(char c, char[] inOrder, int index)
{
Array.IndexOf(Inorder,c) < index;
}

or iteratively as follows:


Node  BuildTree(List<Node> pre, List<Node> in) // Node.left = null; Node.right = null;
{
for (int i = 0; i < pre.Length; i++)
{
int index = i;
int inIndex = Array,indexOf(in, pre[index]);
if ( index + 1 < pre.Length &&
     Array.IndexOf(in, pre[index+1]) < index)
   pre[i].left = pre[index+1];
if (inIndex+1 < in.Length &&
    Array.IndexOf(pre, in[inIndex+1]) >= index)
    pre[i].right = Array.IndexOf(pre, in[inIndex+1]);
}
return pre[0];
}

Today we look at a few more coding problems. Yesterday we said the traversal orders can be used to serialize the tree. If we are given a preorder traveral of a tree, can we verify that the tree is serialized without reconstructing? This means it can be linear in time complexity.
Let us take an example:
    9
 3    2
4 1 # 6
is serialized as 9,3,4,#,#,1,#,#,2,#,6,#,#

Note that we can remove the right most vertices if it has two null leaves and substitute it with null.
If this is mot the case then the parent has a left subtree and we start to do the same with the left sub tree until finally there is only one node remaining and it is null.

bool IsValidBT(List<Node> nodes)
{
bool isValid = false;
  int i = Nodes.Count-1;
  while (i >= 3)
  {
      if (Nodes[i] == null  && Nodes[i-1] == null  && Nodes[i-2] != null){
         nodes.RemoveRange(i-2, 3);
         nodes.Insert(i-2, null);
        i = i - 3;
        continue;
      }
      if(Nodes[i] != null){
          if (Nodes[i+1] == null  && Nodes[i+2] == null){
           nodes.RemoveRange(i, 3);
           nodes.Insert(i, null);
          }
          i=i-1;
        continue;
      }
     i = i -1;
  }
  if (i ==0 && nodes[i] == null) isValid = true;
  return isValid;
}

If we have a binary search tree and we have an inorder and preorder traversals,
then the two traversals can be used to simultaneously find the left and right subtree length of each node.

Today we continue more coding puzzles reviews. One of the problems is about serializing and deserializing a binary tree.
There are many ways to do it. Usually two different orders of traversal of a binary tree can give all the information to deserialize the binary tree. They are also efficient because each node is visited once during a traversal. Another way to do this would be to print the tree level wise with null nodes for missing child nodes of the tree. The level wise ensures one serialization result.
void serialize(Node root, Node delimiter, Node Empty)
{
var q = new Queue<Node>();
q.Enqueue(root);
q.Enqueue(delimiter);

var node = q.Dequeue();
while (node)
{
if (root.left)
      q.Enqueue(root.left) ;
else
      q.Enqueue(Empty); // new node

if (root.right)
      q.Enqueue(root.right);
else
      q.Enqueue(Empty); // new node

node = q.Dequeue();

Console.Write(node.toString());

if (node == delimiter) {q.Enqueue(delimiter);}

}
}

The deserialization now will find all the left or child nodes for every parent nodes even if they are null.

void deserialize(List<Node> nodes, Node delimiter)
{
int level = nodes.Index(nodes.First(x => x == delimiter));
level++;
for (int I = 0; I < nodes.Count() && level < nodes.Count(); I++)
{
   if (nodes[I] != delimiter)
   { nodes[I].left = nodes[level]; level++;
      nodes[I].right = nodes[level]; level++;
   }
   else
        assert nodes[level] ==delimiter
        level++;
}
}

Let's take an example:
   1
2   3
    4  5
1D23DEE45

Today we continue to review a coding problem.
The problem statement:
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
for example if there are five bulbs:
Initially  [ 0, 0, 0, 0, 0]
Round 1 [ 1, 1, 1, 1, 1]
Round 2 [ 1, 0, 1, 0, 1]
Round 3 [ 1, 0, 0, 0, 1]

Round 4 [ 1, 0, 0, 1, 1]

Round 5 [ 1, 0, 0, 1, 0]

The solution:

int bulbSwitch(int n){
      return Math.sqrt(n);
}

The reasoning:
A bulb ends up on only if it is switched an odd number of times.
bulbs 1 to n has a bulb i that is switched in round  d only if d divides i.
bulb i is in a switched on state only if it has an odd number of divisors.
but divisors come in pairs except for squares and pairs returns to original state
so only squares leave a toggled state and the initial state is all off
therefore we count only the squares uptil and inclusive of the number
Thus the answer is Math.sqrt(n)

courtesy: Stefan Pochmann

We implement square root with gradient method. If y ^ 2 = x then y = x / y
And we iteratively improve the approximation
Double SqRt (int n)
{
Double g = n/2;
Double y = n/g;
While(abs (y-g) > 0.001)
{
   g = (g + n/g) /2;
   y = n / g;
}
Return y;
}

Today we continue to review a few more dynamic programming problems. We discussed coin counting problem. Let us look at a variation that involves maximum number of ways in which coins can make a sum. We assume an infinite supply of coins and we could this by backtracking.
void CoinCount(ref List<int> coins, ref List<int>change, int amount, int start, int level)
{

for (int I = start; I < amount; I++)

{

for (int j = 1; i < coins.Count() && j <= amount/coins[I]; j++)

{

for (int k = 0; k < j; k++){
       change[level+k] = coins[i];
}

if (change.sum() == amount) Console.WriteLine("{0} with {1} elements", change.ToString(),
change.Count());

if (change.sum() < amount)
      CoinCount( ref coins, ref change, n, start+1, level+j);

for(int k = 0; k <j; k++){
      change[level+k] = 0;
}
}
From all the change set printed, we can find the the total count as the answer.
Note that we cannot apply the knapsack solution to another coin counting problem earlier we cannot apply a top down greedy choice method because we don't have a criteria to decide upfront how to generate a sequence that satisfies the sum.

The dynamic programming approach builds the solution in a bottom up manner. For each of the given denominations, either the denomination is part of the solution or it isn't. If the denomination is part of the solution, then the solution sub problem shrinks the sum otherwise it shrinks the denominations. If the denomination is part of the solution, then it shrinks the sum from any one of 1 to amount/denomination occurrences. Since there are overlapping subproblems, we could do well to reuse already memoize the computations.

We now look at a different problem which is to reconstruct itinerary. Itineraries consist of source destination pairs. They belong to the same traveler so they all connect. Build the itinerary starting with JFK and in the smallest lexical order.

List<string> GetItinerary(List<Tuple<string, string>> segments)
{
 segment.sort(); // based on source airport comparator

var startItem = segments.find("JFK");
segments.Remove(startItem);

var ret = new List<string>(){startItem.Item1, startItem.Item2};
while (segments.IsEmpty() == False)
{
    startItem = segments.find(startItem.Item2);
    ret.Add(startItem.Item2);
    segments.Remove(startItem);
}
return ret;
}

Allocate minimum number of pages to students
N books
Pi pages i = 1 to N
M students
int GetMinPages(int N, int M, List<int>Pi)
{
assert (Pi.Count() == N);
if (N == 0) return 0;
if (M == 0) return INT_MAX;
min = 0;
for (int i =0; i < N/M;i++)
   int val = GetMinPages(N-i+1, M-1, Pi.Range(i+1,N-i+1)) + Pi.Range(0,i).Sum();
   if val < min
      min = val;
return min;
}