1. Introduction

In this tutorial, we’ll be discovering how to reconstruct a tree from its depth-first traversals. We’ll be using a binary tree as an example to demonstrate and we’ll find out which traversal combinations can be used together to recreate a unique tree.

2. Traversals Which Can Be Used to Reconstruct a Tree

As we know, binary trees can be represented by different types of traversals. These traversals can be used to reconstruct a tree. However, usually, one type of traversal is not enough to reconstruct a tree, and we must use two traversals in combination.

The following are the types of depth-first traversals which we can use in combination to reconstruct a tree:

  • In-order and pre-order
  • In-order and post-order
  • Pre-order and post-order – can be used only if the tree is a full binary tree.

As we can see, the in-order traversal is always essential to be able to get a unique tree, unless a binary tree is a full binary tree. In such a case, we can actually reconstruct it from it pre-order and post-order traversal. We’ll learn more about this later in this tutorial.

3. A Practical Example

We’ll be using the following tree as our example – we’ll try to reconstruct it using different traversals methods:

full tree

Using the different traversal methods on this tree, we get the following traversal sequences:

traversals 1

4. Reconstructing a Tree From Its Pre-Order and In-Order

To reconstruct our tree from its pre-order and in-order sequences, we start by looking at the first element of the pre-order sequence. Since pre-order traverses a tree starting with the root, then the left node, then the right node, we know that the first element 6 is the root of our tree.

Next, we look at the in-order sequence and locate the root 6. Any elements in the in-order sequence to the left of 6 belong to the left sub-tree. Whereas any elements to the right of 6 belong to its right sub-tree:

preorder inorder step 1

So now we can start building our tree partially to look like this:

preorder inorder partial tree step

Next, we go back to the pre-order sequence and take the next element – which is 3. We already know from our previous step that 3 belongs in the left sub-tree. If we find 3 in the in-order sequence we’ll find that it has 2 and 4 to its left and right sub-tree respectively. i.e. 3 is the root node of the left sub-tree and 2 and 4 are left and right nodes of 3:

preorder inorder step 2

Now our tree is shaping up nicely with the left side of the tree entirely built:

preorder inorder partial tree step 2-1

Next in the pre-order sequence is 19, which if we find in the in-order sequence gives us the following tree:

preorder inorder step 3

preorder inorder partial tree step 3

As we can see from the previous steps, there’s a recursive pattern emerging in which we traverse the pre-order sequence and for each node position within the in-order sequence and use it to determine its left and right children. 

Finally, the next number in the pre-order is 12, and looking at the in-order sequence tells us that nodes 7 and 15 are its left and right children respectively which gives us the final representation of the tree:

full tree

4.1. Algorithm for Reconstructing a Tree From Its Pre-Order and In-Order

Let’s take a look at the following algorithm which describes the logic in pseudo-code. Note, that we’re assuming the following in the algorithm:

  • Nodes are a construct with references to left and right child nodes
  • indexOf() is a method used to find the index of an element in an array
  • length will give us the length of an array
algorithm BuildTree(preorder, inorder):
    // INPUT
    //    preorder = array of nodes in preorder traversal
    //    inorder = array of nodes in inorder traversal
    //    preorderIndex = global variable initialized to 0
    // OUTPUT
    //    Reconstructs the binary tree from preorder and inorder traversal and returns the root node
   
    node <- preorder[preorderIndex]
    preorderIndex <- preorderIndex + 1
    
    inorderIndex <- the index of nodeValue in inorder
    
    inorderLeft <- inorder[0 : inorderIndex]
    inorderRight <- inorder[inorderIndex + 1 : length(inorder)]
    
    if length(inorderLeft) = 0 and length(inorderRight) = 0:
        return node
    
    node.left <- buildTree(preorder, inorderLeft)
    node.right <- buildTree(preorder, inorderRight)
    
    return node

5. Reconstructing a Tree From Its Post-Order and In-Order

Reconstructing a tree from a post-order and in-order sequence is very similar to reconstructing it using the pre-order and in-order sequence. However, in this case, we’re going to start by looking at the last element in the post-order sequence. Since a post-order sequence always ends with the root node, we know the last element 6 has to be the root of our tree.

Similar to our previous example, in the next step we find node 6 in the in-order sequence and find out the node which belongs to its left and right children.

We’ll continue along the post-order sequence from its last element and repeating these steps until we’ve built up the entire tree:

post order inorder all steps 1

5.1. Algorithm for Reconstructing a Tree From Its Post-Order and In-Order

The pseudo-code for reconstructing a tree from its post-order and in-order sequences is very similar to our previous pseudo-code example with the difference being in the fact that we start traversing the post-order sequence from back to front and we also start populating the right tree first. This is in keeping with the fact that the post-order traversal traveled backward will give us root, left, and then right nodes. This gives us the following:

algorithm BuildTreePostIn(postorder, inorder):
    // INPUT
    //    postorder = array of nodes in postorder traversal
    //    inorder = array of nodes in inorder traversal
    //    postorderIndex = global variable initialized to the infrx of the last node: length(postorder) - 1
    // OUTPUT
    //    reconstructs the binary tree from postorder and inorder traversal and returns the root node
    
    node <- postorder[postorderIndex]
    preorderIndex <- preorderIndex - 1
    
    inorderIndex <- the index of nodeValue in inorder
    
    inorderLeft <- inorder[0 : inorderIndex]
    inorderRight <- inorder[inorderIndex + 1 : length(inorder)]
    
    if length(inorderRight) = 0 and length(inorderLeft) = 0:
        return node
    
    node.right <- buildTreePostIn(postorder, inorderRight)
    node.left <- buildTreePostIn(postorder, inorderLeft)
    
    return node

6. Reconstructing a Tree From Its Post-Order and Pre-Order

Lastly, we’re going to see how we can reconstruct a tree from its pre-order and post-order sequence. In order for us to be able to reconstruct a tree from its pre-order and post-order our tree must be a full binary tree. That means each node in the tree must have 0 or 2 nodes.

If you’re wondering why these two sequences can’t be used for binary trees in general, let’s take a look at the two binary trees below which are not full:

non full binary tree

Since these two trees have an identical pre-order and post-order sequence, it’s not possible for us to reconstruct each tree individually from those two sequences alone because the pre-order and post-order sequences can’t tell us if a node is a left or a right child.

Because our example tree is actually a full binary tree, we can, in fact, reconstruct it from its pre-order and post-order alone.

We start by determining the node from the first element of the pre-order sequence. Then because we know that we’re dealing with a full binary tree, we can deduce that the next element 3 in the pre-order sequence is surely the left child of the root node.

Now, if we find 3 in the post-order sequence we can use its position to determine which elements are children of 3:

preorder postorder 1

Using this information, we get the following partial tree:

preorder postorder partial tree step 1-1

The next element after 3 in the pre-order is 2. knowing that this is a full binary tree we can conclude that 2 is the left child of 3 which leaves 4 to be the right child of 3:

preorder postorder 2

Next in the pre-order sequence is number 19, whose position in the post-order sequence shows as the root of the left sub-tree:

preorder postorder 3

Based on this, we can rearrange our tree to give us the following:

preorder postorder partial tree step 4

Once again, here we can see a recursive pattern which we’re using to build the tree in iterations. First, we use the pre-order sequence to go through each node. Then we use the post-order sequence to find the children of each node. The fact that the binary tree is full helps us determine which node is the left child from the pre-order sequence.

6.1. Algorithm for Reconstructing a Tree From Its Post-Order and Pre-Order

Now lets see how we can describes the algorithm with which we can recursively construct a tree from its pre-order and post-order sequences:

algorithm BuildTreePrePost(preorde, postorder):
    // INPUT
    //    preorder = array of nodes in preorder traversal
    //    postorder = array of nodes in postorder traversal
    //    preorderIndex = global variable initialized to 0
    // OUTPUT
    //    reconstructs the full binary tree from preorder and postorder traversal and returns the root node
    
    if preorderIndex >= length(preorder):
        return null
    
    node <- preorder[preorderIndex]
    if preorderIndex >= length(preorder) or nodeValue = postorder[length(postorder) - 1]:
        preorderIndex <- preorderIndex + 1
        return node
    
    leftChildValue <- preorder[preorderIndex]
    postorderLeftIndex <- indexOf(postorder, leftChildValue)
    
    postorderLeft <- postorder[0 : postorderLeftIndex]
    postorderRight <- postorder[postorderLeftIndex + 1 : length(postorder) - 1]
    
    node.left <- buildTreePrePost(preorder, postorderLeft)
    node.right <- buildTreePrePost(preorder, postorderRight)
    
    return node

7. Summary

In this tutorial, we discovered various ways of reconstructing a binary tree from its depth-first traversals. In addition, we implemented our knowledge on an example tree and learned the limitation of using pre-order and post-order traversal only to reconstruct a tree.


» 下一篇: 分支定界算法