Construct tree with pre-order traversal given

Question

A special type of tree is given where all leaves are marked with L and others are marked with N. Every node can have 0 or at most 2 nodes. The preorder traversal of the tree is given.

Give an algorithm to build the tree from this traversal.

Answer 1

This is the preorder traversal algorithm:

Preorder(T)
  if (T is not null)
    print T.label
    Preorder(T.left)
    Preorder(T.right)

Let's try to find an algorithm for an input of NNLLNL.

Obviously the label of the root is printed first. So you know the root has label N. Now the algorithm recurses on the left subtree. This is also N according to the input. Recurse on the left subtree of that, which is L. Now you have to backtrack, because you've reached a leaf. The next position in the input is also L, so the current node has a right child labeled with L. Backtrack once. Backtrack again, because you've added all the children of the current node (max 2 children). Now you're at the root again. You have to go right, because you already went left. According to the input, this is N. So the right child of the root is N. The left child of that will be L. This is your tree:

       N
     /   \
    N     N
   / \   /
  L   L L

Note that the solution is not necessarily unique, but this will get you a possible solution.

Pseudocode:

k = 0
input = ... get preorder traversal vector from user ...
Reconstruct(T)
  if input[k] == N
    T = new node with label N
    k = k + 1 
    Reconstruct(T.left)
    Reconstruct(T.right)
  else 
    T = new node with label L
    T.left = T.right = null
    k = k + 1

Call with a null node.

Follow-up question: given both the preorder and the inorder traversal of a binary tree containing distinct node labels, how can you uniquely reconstruct the tree?