CareerCup

I'm surprised, that this is a phone interview question.

1. Traverse the tree in Pre-Order form, push each node into a List.
2. For missing nodes, push null into the list.

public static List<Integer> getList(Tree root){
		List<Integer> res = new ArrayList<>();
		if(root == null) return res;
		preOrder(root, res);
		return res;
	}
	
	public static void preOrder(Tree root, List<Integer> res){
		if(root == null){
			res.add(null);
			return;
		}
		res.add(root.data);
		preOrder(root.left, res);
		preOrder(root.right, res);
	}

Then re-construct, the Tree back from the List.

public static Tree getTree(List<Integer> res){
		Tree t = getTreeHelp(res);
		return t;
	}
	
	
	private static Tree getTreeHelp(List<Integer> res){
		if(res.size() == 0) return null;
		Integer key = res.remove(0);
		if(key == null) return null;
		Tree root = new Tree(key);
		root.left = getTreeHelp(res);
		root.right = getTreeHelp(res);
		return root;
	}

public static List<Integer> store(Node root) {
    List<Integer> sol = new LinkedList<Integer>();
    storeTree(root, sol);
    return sol;
  }
  
  private static void storeTree(Node root, List<Integer> sol) {
    if(root == null) {
      sol.add(null);
      return;
    }
    root.add(root.value);'
    storeTree(root.left, sol);
    storeTree(root.right, sol);
  }
  // 5 3 1 null null null 2 6 null null 1 null null
  
  public static Node restore(List<Integer> list) {
    if (list.peek(0) == null)
      return list.poll(0); 
  
    Node n = new Node(list.poll(0));
    n.left = restore(list);
    n.right = restore(list);
    return n;
  }

1. Traverse the tree in Level Order traversal
2. Create a new tree and just perform AddToTree operation on each item

public List<int> Store(Node ptr)
            { 
                List<int> treeList = new List<int>();
                LevelOrder(ptr, treeList);
                return treeList;
            }

            private void LevelOrder(Node source, List<int> treeList)
            {
                HashSet<int> visited = new HashSet<int>();
                Queue<Node> nextToVisit = new Queue<Node>();
                nextToVisit.Enqueue(source);

                while (nextToVisit.Count > 0)
                {
                    Node ptr = nextToVisit.Dequeue();

                    if (ptr == null)
                    {
                        treeList.Add(-1);
                        continue;
                    }
                    treeList.Add(ptr.val);

                    nextToVisit.Enqueue(ptr.left);
                    nextToVisit.Enqueue(ptr.right);
                }
            }

Node newRoot = null;
            private void AddToRestoredTree(int val)
            {
                if (newRoot == null)
                {
                    newRoot = CreateNewNode(val);
                }
                else
                {
                    Node ptr = newRoot;
                    while (ptr != null)
                    {
                        if (val < ptr.val)
                        {
                            if (ptr.left != null)
                            {
                                ptr = ptr.left;
                            }
                            else
                            {
                                ptr.left = CreateNewNode(val);
                                break;
                            }
                        }
                        else
                        {
                            if (ptr.right != null)
                            {
                                ptr = ptr.right;
                            }
                            else
                            {
                                ptr.right = CreateNewNode(val);
                                break;
                            }
                        }
                    }
                }
            }

void Store(Node const *n, vector<int> &list)
{
	if (n == NULL) {
		list.push_back(numeric_limits<int>::min());
		return;
	}
	list.push_back(n->val_);
	Store(n->left_, list);
	Store(n->right_, list);
}

Node *Restore(vector<int> const &list, int &idx)
{
	if (list[idx] == numeric_limits<int>::min()) {
		++idx;
		return NULL;
	}
	Node *n = new Node(list[idx++]);
	n->left_ = Restore(list, idx);
	n->right_ = Restore(list, idx);
	return n;
}

public static List<Integer> store(Node root) {
    List<Integer> sol = new LinkedList<Integer>();
    storeTree(root, sol);
    return sol;
  }
  
  private static void storeTree(Node root, List<Integer> sol) {
    if(root == null) {
      sol.add(null);
      return;
    }
    root.add(root.value);'
    storeTree(root.left, sol);
    storeTree(root.right, sol);
  }
  // 5 3 1 null null null 2 6 null null 1 null null
  
  public static Node restore(List<Integer> list) {
    if (list.peek(0) == null)
      return list.poll(0); 
  
    Node n = new Node(list.poll(0));
    n.left = restore(list);
    n.right = restore(list);
    return n;

}

I don't think the second part of the question is well defined. There are many trees that will have the same list representation. Consider the following trees

# 0
# \
# 0

and
# 0
# /
#0

my understanding is that both of these tress have to have a list representation of [0,0], so they are indistinguishable.