Understanding pseudocode for constructing a tree from order traversal

Question

I need to do something similar to the task described in this question:
Build a tree with a given order

Here's a really useful answer, but I don’t completely understand the pseudo code, so I was wondering if anyone could help me describe what is going on.

k = 0 // Initialize input = ... get preorder traversal vector from user ... // Get input Reconstruct(T) // Reconstruct method with tree input if input[k] == N // If element of input is N T = new node with label N // Make a new node with label N in tree T k = k + 1 // Increment k for next loop (Is this whole thing a loop? or a method call?) Reconstruct(T.left) // ????? Reconstruct(T.right) // ????? else // If element of input is L T = new node with label L // Make a new node with label L in tree T T.left = T.right = null // ????? k = k + 1 // Increment k for next loop 

I wrote my understanding of things in the comments, and I would really appreciate it if someone could verify that my understanding is correct and what the bits of the question do. Also, is this pseudo-code a new tree passing through the input and backtracking whenever L occurs in the input? Or is it restoring an existing binary tree?

Answer 1

There is no cycle. k is a global reach variable that can be accessed within Reconstruct(T) . This is just the current character array index (input string).

As explained in the question you referenced ( Design a tree with a preview ), For the correct algorithm, make the left-child number of the node, and then the right-child number. This is what you see in the true if section. If the current node is a leaf, L , then do not give it children and return to the calling function.

What this function does is follow the left edge of the tree, adding children to all nodes of N and not adding children to all nodes of L (aka leaves) until the line ends.

Edit: when the author of the pseudocode says T.left = T.right = null , it means that at the moment the current node does not have a left or right child (because it is a sheet). This is just a statement and does not have to be in code.