Construct tree with pre-order traversal given
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?