Construct Binary Tree From Preorder and Inorder Traversals

Given the preorder and inorder traversal arrays of a tree, construct it.

For example,

Given

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

You need to construct the below tree:

leetcode.com

you need to return the root node of the above tree in your code.

Try it here:

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Solution:

Hint: Using root node from preorder traversal , find left and right trees in inorder traversal recursively.

In a preorder traversal you take the root node first , then the left node and then the right node.
The traversal goes like Root -> Left -> Right

In an inorder traversal you take the left node first , then the root node and then the right node.

The traversal goes like Left -> Root -> Right.

As you can infer from the two directions.

The first node in preorder traversal is the root.

Take this.

Find this root in the inorder traversal.

The left to this root is the left node/subtree and the right to this root is the right node/subtree.

So using the root from preorder we can find its left subtree and right subtree from inorder.

Use this logic.

For each subtree , again take the root from preorder and the left and right subtree from inorder.

Continue this recursively until no more nodes are left.

Let’s take our example:

preorder – [3 , 9 ,20,15,7]

inorder – [9,3,15,20,7]

As already mentioned the first node in preorder is the root node.

It is 3 in the above example.

Check for 3 in the inorder traversal.

It is in the second index.

All the elements left to this is the left subtree of the node 3 [9]

And all the elements right to this is the right subtree of the node 3 [15,20,7]

Now take the left subtree [9].

There is only one node in this tree , so it needs no further processing.

We have got one root node 3 and its left node 9 till now.

Now take the right subtree

inorder – [15,20,7]

Find the root node from the preorder [3,9,20,15,7] , we have already processed 3 and 9.

So the next root node is 20.

Find the position of 20 in the unprocessed inorder array [15,20,7].

It is in the middle.

So the elements left to 20 forms the left subtree of node 20 [15]

And the elements right to 20 forms the right subtree of node 20 [7]

[15] and [7] have no further children.

So we can stop processing and return the root node 3 which has all the connections now.

Here is the code to do it:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    Map<Integer,Integer> inorderIndexes = new HashMap<>();
    int preorderindex=0;
    
    int[] preorderGlobal;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        preorderGlobal = preorder;
        
        for(int i=0;i<inorder.length;i++){
            
            
            inorderIndexes.put(inorder[i],i);
        }
        
        return build(0,preorder.length-1);
        
    }
    
    
    public TreeNode build(int left,int right){
        
        
        if(left > right) return null;
        
        
        TreeNode node = new TreeNode(preorderGlobal[preorderindex++]);
        
         
        node.left = build(left,inorderIndexes.get(node.val)-1);
        
        node.right = build(inorderIndexes.get(node.val)+1,right);
        
        return node;
    }
}

Data structures used:

  1. Map

We use a global map to store the indices of each element in the inorder traversal array.

We need this to find out the left and right subtrees.

2. Integer variable to find out the root node.

We use a global integer variable preoorderindex to fetch each root node from the preorder traversal.

This node will be then searched for in the inorder array to find out the left and right subtrees.

3. An integer array to store preorder

We are going to use recursion to solve this problem.

We are going to repeatedly scan preorder array during each recursion call.

So to keep things simple , the preorder array is populated into a global integer array.

Algorithm:

  1. Declare the data structures as discussed above
  2. Populate the position of each element in the inorder array in a map
  3. Call a recursive function with the first index (left) and the last index position (right) in the order array. The recursive function does the following:
  4. If left index is greater than right index then we don’t have any elements to process in the order array so return null.
  5. Get the current root node (starts from index 0) from the preorder array and build a tree node.
  6. Assign the left of the node to the node returned by a recursive call with the current left index and the index of one element before the currently created node in the inorder array. This represents the range of the left subtree in the inorder array.
  7. Assign the right of the node to the node returned by a recursive call with the index of one element next to the currently created node in the inorder array and the current right index. This represents the range of the right subtree in the inorder array.
  8. Return current node.

Let’s see how this algorithm works for our input:

preorder – [3,9,20,15,7]

inorder – [9,3,15,20,7]

We will focus on the build() method which has the core recursive logic.

We have the map with the element indexes already constructed :

inorderIndexes:

9 – 0

3 – 1

15 – 2

20 -3

7 – 4

We also have the preorder array:

[3,9,20,15,7]

First iteration:

build(0,4):

0 not greater than 4 ,

So

TreeNode node = new TreeNode(preorder[0]) = new TreeNode(3)

node.left = build(0, inorderIndexes.get(3)-1) = build (0,0);

node.right = build(inorderIndexes.get(3) + 1,right) = build (2,4)

Second iteration:

build(0,0)

0 not greater than 0 ,

So

TreeNode node = new TreeNode(9)

node.left = build (0,-1) –> here left index is greater than right index so this call will return immediately

node.right = build(1,0) –> here also left index is greaterthan right index so this call will return immediately.

Third iteration

build(2,4):

2 not greater than 4,

So

TreeNode node = new TreeNode(20)

node.left = build(2,2)

node.right = build(4,4)

Fourth iteration:

build(2,2):

2 not greater than 2,

So,

TreeNode node = new TreeNode(15)

node.left = build(2,1) –> left not greater than right here

node.right = build(3,2) – –> left not greater than right here

Fifth iteration:

build(4,4)

4 not greater than 4 ,

So

TreeNode node = new TreeNode(7)

node.left = build(4,3) –> left not greater than right

noderight = build(5,4) –> left not greater than right.

There are no elements in the recursion stack , so the call stops here.

Time complexity:

We iterate through all the elements once so time complexity is O(n)

Space complexity:

We use a map of size n and the recursive calls take a size of n in the worstcase.

So space complexity is O(2n) , ignoring the constant it is O(n)

That’s it!


Posted

in

, , ,

by

Comments

Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading