Problem of arranging ill behaved children in a straight line

Your job is to arrange n ill-behaved children in a straight line, facing front. You are given a list of m statements of the form “i hates j”. If i hates j, then you do not want put i somewhere behind j, because then i is capable of throwing something at j.

Above problem can be solved by modeling above problem as direct graph where a directed edge exists between two children i and j if i hates j. Doing a Topological sort on this graph is going to give us the answer. Here is how Topological sort works:

1. Do a DFS on above graph.
2. Associate "finishing time" with each node while doing DFS.
3. Return the nodes in the decreasing order of "finishing time"

Iterative postorder traversal of Binary Tree Part-I

Iterative postorder traversal of Binary tree is tricky.  What makes it tricky is having to visit the same node multiple times and taking different actions on different visit. There are multiple ways of doing it. I have few of them coded in C# here.

Here is my node structure. Note I am using array to hold left and right pointers instead of Left and Right. Having children defined this way, reduces redundant code.

   1:  class Node

   2:  {

   3:      public int key;

   4:      public Node[] children = new Node[2];

   5:  }

I am going to use to Stack to keep track of nodes and associated visit count. The StackEntry is defined as follows

   1:  class StackEntry

   2:  {

   3:      public Node node;

   4:      public int visitcount;

   5:  }

Here is the code for PostOrder traversal of Binary Tree

   1:  public void PostOrder()

   2:  {

   3:      Stack<StackEntry> stack = new Stack<StackEntry>();

   4:      stack.Push(new StackEntry { node = root });

   5:      while (stack.Count > 0)

   6:      {

   7:          var top = stack.Peek();

   8:          if (top.visitcount < 2)

   9:          {

  10:              int direction = top.visitcount++;

  11:              if (top.node.children[direction] != null)

  12:              {

  13:                  stack.Push(new StackEntry { node = top.node.children[direction] });

  14:              }

  15:          }

  16:          else

  17:          {

  18:              stack.Pop();

  19:              Console.Write(" {0} ", top.node.key);

  20:          }

  21:      }

  22:  }

Above algorithm is doing following things:

1. Initially root is wrapped inside StackEntry and pushed onto the stack.
2. Inside while loop we look at stack's top element's visit count. 
3. If visitcount == 0, then we push top element's left child provided it is non-null and increment the visitcount.
4. If visitcount == 1, then we push top element's right child provided it is non-null and increment the visitcount.
5. If visitcount ==2, then we pop the element and print its value.

tryingout: tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

tryingout: tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

Recreating Binary Tree from Inorder and Postorder traversal data

This is continuation of earlier post about recreating Binary tree from given Preorder and Inorder data. This blog post has C# code from recreating the tree from inorder and postorder. The algo here is almost same as previous one except we start reading the postOrder data from right hand side as right most node is post-order transversal is Root node.

   1:  static Node DeserializeInorderPost(int[] inorder, int[] postorder)

   2:  {

   3:      int[] mapping = new int[inorder.Length];

   4:      for (int i = 0; i < inorder.Length; i++)

   5:      {

   6:          mapping[inorder[i]] = i;

   7:      }

   8:      int readPtr = inorder.Length -1;

   9:      return DeserializeInorderPost(inorder, postorder, mapping, 0, inorder.Length, ref readPtr);

  10:  }

  11:   

  12:  static Node DeserializeInorderPost(int[] inorder, int[] postorder, int[] mapping, int start, int end, ref int readPtr)

  13:  {

  14:      if (end == start)

  15:      {

  16:          return null;

  17:      }

  18:   

  19:      Node root = new Node { data = postorder[readPtr--] };

  20:      int divider = mapping[root.data];

  21:      root.right = DeserializeInorderPost(inorder, postorder, mapping, divider+1, end, ref readPtr);

  22:      root.left = DeserializeInorderPost(inorder, postorder, mapping, start, divider, ref readPtr);

  23:      return root;

  24:  }

Deserializing Binary Tree from inorder and preorder traversal

Suppose we are given preorder and inorder tree traversal data, is it possible to recreate original Binary tree? Yes it is.

   1:  static Node DeserializePreInorder(int[] preorder, int[] inorder)

   2:  {

   3:      int[] mapping = new int[inorder.Length];

   4:      for (int i = 0; i < inorder.Length; i++)

   5:      {

   6:          mapping[inorder[i]] = i;

   7:      }

   8:      int start = 0;

   9:      return DeserializePreInorder(preorder, inorder, mapping, 0, inorder.Length, ref start);

  10:  }

  11:   

  12:  static Node DeserializePreInorder(int[] preorder, int[] inorder, int[] mapping, int low, int high, ref int readPointer)

  13:  {

  14:      if (low == high)

  15:      {

  16:          return null;

  17:      }

  18:      Node root = new Node { data = preorder[readPointer++] };

  19:      int dividerIndex = mapping[root.data];

  20:      root.left = DeserializePreInorder(preorder, inorder, mapping, low, dividerIndex, ref readPointer);

  21:      root.right = DeserializePreInorder(preorder, inorder, mapping, dividerIndex + 1, high, ref readPointer);

  22:      return root;

  23:  }

For detailed discussion see here