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:
Using the different traversal methods on this tree, we get the following traversal sequences:
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:
So now we can start building our tree partially to look like this:
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:
Now our tree is shaping up nicely with the left side of the tree entirely built:
Next in the pre-order sequence is 19, which if we find in the in-order sequence gives us the following tree:
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:
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:
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:
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:
Using this information, we get the following partial tree:
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:
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:
Based on this, we can rearrange our tree to give us the following:
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.