There is binary tree with special property that all its inner node have val = 'N' and all leaves have val = 'L'. Given its preorder. construct the tree and return the root node.
every node can either have two children or no child
1
votes
2 Answers
5
votes
Recursion is your friend.
Tree TreeFromPreOrder(Stream t) {
switch (t.GetNext()) {
case Leaf: return new LeafNode;
case InternalNode:
Node n = new Node;
n.Left = TreeFromPreOrder(t);
n.Right = TreeFromPreOrder(t);
return n;
default:
throw BadPreOrderException;
}
}
Looking at it as a recursive method, it becomes easy to see how do other things.
For instance, say we wanted to print the InOrder traversal. The code will look something like this:
void PrintInorderFromPreOrder(Stream t) {
Node n = new Node(t.GetNext());
switch (n.Type) {
case Leaf: return;
case InternalNode:
PrintInorderFromPreOrder(t);
print(n.Value);
PrintInorderFromPreOrder(t);
default:
throw BadPreOrderException;
}
}
Also, I would like to mention that this is not that artificial. This type of representation can actually be used to save space when we need to serialize a binary tree: Efficient Array Storage for Binary Tree.
1
votes
Just the basic idea: keep a stack where the head is the "current" node and read sequentially the string representing the preorder.
Now, if you encounter a 'L', then it means the "current" node has as a child a leaf, so you can "switch" to the right child and resuming building the corresponding subtree, pushing the root of that subtree; if, when encountering a 'L', the "current node" has already two children, pop an element from the stack.
