Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Construct Binary Tree Problem

Problem Statement:

Inorder traversal - Process all nodes of a binary tree by recursively processing the left subtree, then processing the root, and finally the right subtree.

Preorder traversal - Process all nodes of a binary tree by recursively processing the root, then processing the left subtree, and finally the right subtree.

Given the inorder and preorder traversal of a valid binary tree, you have to construct the binary tree.

Input Format:

You are given two integer array named inorder and preorder of size n, containing positive values

Output Format:

Return root pointer of the constructed binary tree.

Constraints:

• 0

• 1

• Values stored in the binary tree are unique.

Sample Test Cases:

Sample Test Case 1:

Sample Input 1:

inorder = [2, 1, 3] and preorder = [1, 2, 3]

Sample Output 1:

           1

          /  \

        2    3

Explanation 1:

In this case, Binary tree will be look like as given above.

Return the pointer of root node of constructed binary tree. In this case root treenode has value '1'.

Sample Test Case 2:

Sample Input 2:

inorder = [3, 2, 1, 5, 4, 6] and preorder = [1, 2, 3, 4, 5, 6]

Sample Output 2:

           1

          /  \

        2    4

       /     /  \

     3    5    6

Solution

We will learn recursive approach by taking an example:

Let's take example from sample input:

inorder[] = [3, 2, 1, 5, 4, 6]

preorder[] = [1, 2, 3, 4, 5, 6]

Here, as per preorder traversal definition it traverse the tree recursively by travesing the root first, then left subtree and then right subtree.

• So, we can say that first value of preorder[] is root node value of binary tree, here its 1.

• Now, search the index of that value in inorder[]. Say you find it at position i, once you find it, make note of elements that are left to I (This will construct the left subtree) and elements which are right to i (This will construct the right subtree).

See the above steps and recursively build left subtree and link it root.left and recursively build right subtree and link it root.right.

Let's have a look how recursion will happen in our case,

Root:

(1's position confirmed)

           1

          /  \

   [3,2]    [5,4,6]

In the left subtree of the root:

(2's position confirmed)

           1

          /  \

        2   [5,4,6]

        |

       [3]

(3's position confirmed)

           1

          /  \

        2    [5,4,6]

       /

     3

In the right subtree of the root:

(4's position confirmed)

           1

          /  \

        2    4

       /      |

     3      [5,6]

(5's position confirmed)

           1

          /  \

        2    4

       /     / |

     3    5 [6]

(6's position confirmed)

           1

          /  \

        2    4

       /     /  \

     3    5    6

So, the above tree will be our binary tree for given test case. Return the root treenode which is 1 in this case.

1) brute_solution.java

Time Complexity:

O(n^2), here n is length of given inorder[] or preorder[] array, in other words count of total treenodes of binary tree.

Suppose you are given tree in which all nodes have only left child, there is no right child of any treenode, then for every preorder[] value it will take O(n) to search in inorder[].

So, In worst case time complexity will be O(n^2).

Auxiliary Space Used:

O(n).

As we are constructing the binary tree and storing values in treenodes. Every node will take constant space to store value and addresses for left and right treenode. So, it will be O(n).

Space Complexity:

O(n).

As input is O(n) and auxiliary space used is also O(n).

So, O(n) + O(n) -> O(n).


// -------- START --------

    static int current_index;
    
    public static TreeNode constructBinaryTree(int inorder[], int preorder[]) {
        
        int arr_len = inorder.length;
        
        current_index = 0;
        
        return utilConstructBinaryTree(inorder, preorder, 0, arr_len - 1);
        
    }
    
        /* Recursive function to construct a binary tree using Inorder traversal 'inorder[]'
        and Preorder traversal 'preorder[]'. Initial value of 'start' and 'end' should be '0' 
        and 'arr_len-1'*/
    
       // Initially 'current_index' should be '0'.

    /* Here, 'start' and 'end' values indicate search range in 'inorder[]' for value at index 
          'current_index' of 'preorder[]'.*/

    // Create 'root' node of value at index 'current_index' of 'preorder[]'.

    /* If value found at index 'x' in 'inorder[]', it means values of range [start, x] of 'inorder[]' will 
        lie in left subtree of root node and values of range [x, end] of 'inorder[]' will lie 
        in right subtree of root node.*/


    public static TreeNode utilConstructBinaryTree(int inorder[], int preorder[], int start, int end) {


        if(start>end)
            return null;
        
        /* Pick current node from Preorder traversal using current_index 
            and increment current_index */
        
        TreeNode root = new TreeNode(preorder[current_index++]);

        /* If above node has no children then return */
        
        if(start == end) {
            return root;
        }
        
        /* Else find the index of this node in Inorder traversal */
        
        int index_of_inorder = findIndex(inorder, root.value, start, end);
        
        /* Using index in Inorder traversal, construct left and 
            right subtrees */
        
        root.left = utilConstructBinaryTree(inorder, preorder, start, index_of_inorder - 1);
        root.right = utilConstructBinaryTree(inorder, preorder, index_of_inorder + 1, end);
        
        return root;
    }
    
    /* This function is to search 'value' in 'inorder' in the range [start, end] and 
       returns index of that 'value'. */
    
    public static int findIndex(int inorder[], int value, int start, int end) {
        
        while(start<=end) {
            
            if(inorder[start] == value) {
                return start;
            }
            
            start++;
        }
        
        return -1;
        
    }
    
    // -------- END --------

2) optimal_solution.java

Time Complexity:

O(n).

We are using hashmap to search index of value in inorder[], and hashmap takes O(1) time (search in hash map can be upto O(n) in worst case, when values are in wide range and carefullly chosen) to search value. So, in every case time complexity will be O(n).

Auxiliary Space Used:

O(n).

As we are constructing binary tree and storing value in treenode, so every node will take constant space to store value and addresses for left and right treenode. Here, we are using hashmap to store inorder[] values with index and it will take O(n) space to store <value,index> pair. So, Auxiliary space will be O(n) + O(n) -> O(n).</value,index>

Space Compelxity:

O(n).

As input is O(n) and auxiliary space used is also O(n).

So, O(n) + O(n) -> O(n).


// -------- START --------
    
    static int current_index;

    
    public static TreeNode constructBinaryTree(int inorder[], int preorder[]) {

        int arr_len = inorder.length;
        
        /* HashMap to store values of 'inorder[]' with index. So, here key and value pair 
            of hashmap will be value and index pair of 'inorder[]'. */
        
        HashMap value_hash_inorder = new HashMap();
        
        // Storing value and index pair of 'inorder[]' in hashmap.

        for(int i = 0 ; i value_hash_inorder) {

        if(start>end)
            return null;

        /* Pick current node from Preorder traversal using current_index 
        and increment current_index */
        
        TreeNode root = new TreeNode(preorder[current_index++]);
        
        /* If above node has no children then return */

        if(start == end) {
            return root;
        }

        /* Else find the index of this node in Inorder traversal */
        int index_of_inorder = value_hash_inorder.get(root.value);
        
        root.left = utilConstructBinaryTree(
                inorder, preorder, start, index_of_inorder - 1, value_hash_inorder);
        root.right = utilConstructBinaryTree(
                inorder, preorder, index_of_inorder + 1, end, value_hash_inorder);

        return root;
    }
    
    // -------- END --------

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Construct Binary Tree Problem

Problem Statement:

Inorder traversal - Process all nodes of a binary tree by recursively processing the left subtree, then processing the root, and finally the right subtree.

Preorder traversal - Process all nodes of a binary tree by recursively processing the root, then processing the left subtree, and finally the right subtree.

Given the inorder and preorder traversal of a valid binary tree, you have to construct the binary tree.

Input Format:

You are given two integer array named inorder and preorder of size n, containing positive values

Output Format:

Return root pointer of the constructed binary tree.

Constraints:

• 0

• 1

• Values stored in the binary tree are unique.

Sample Test Cases:

Sample Test Case 1:

Sample Input 1:

inorder = [2, 1, 3] and preorder = [1, 2, 3]

Sample Output 1:

           1

          /  \

        2    3

Explanation 1:

In this case, Binary tree will be look like as given above.

Return the pointer of root node of constructed binary tree. In this case root treenode has value '1'.

Sample Test Case 2:

Sample Input 2:

inorder = [3, 2, 1, 5, 4, 6] and preorder = [1, 2, 3, 4, 5, 6]

Sample Output 2:

           1

          /  \

        2    4

       /     /  \

     3    5    6

Solution

We will learn recursive approach by taking an example:

Let's take example from sample input:

inorder[] = [3, 2, 1, 5, 4, 6]

preorder[] = [1, 2, 3, 4, 5, 6]

Here, as per preorder traversal definition it traverse the tree recursively by travesing the root first, then left subtree and then right subtree.

• So, we can say that first value of preorder[] is root node value of binary tree, here its 1.

• Now, search the index of that value in inorder[]. Say you find it at position i, once you find it, make note of elements that are left to I (This will construct the left subtree) and elements which are right to i (This will construct the right subtree).

See the above steps and recursively build left subtree and link it root.left and recursively build right subtree and link it root.right.

Let's have a look how recursion will happen in our case,

Root:

(1's position confirmed)

           1

          /  \

   [3,2]    [5,4,6]

In the left subtree of the root:

(2's position confirmed)

           1

          /  \

        2   [5,4,6]

        |

       [3]

(3's position confirmed)

           1

          /  \

        2    [5,4,6]

       /

     3

In the right subtree of the root:

(4's position confirmed)

           1

          /  \

        2    4

       /      |

     3      [5,6]

(5's position confirmed)

           1

          /  \

        2    4

       /     / |

     3    5 [6]

(6's position confirmed)

           1

          /  \

        2    4

       /     /  \

     3    5    6

So, the above tree will be our binary tree for given test case. Return the root treenode which is 1 in this case.

1) brute_solution.java

Time Complexity:

O(n^2), here n is length of given inorder[] or preorder[] array, in other words count of total treenodes of binary tree.

Suppose you are given tree in which all nodes have only left child, there is no right child of any treenode, then for every preorder[] value it will take O(n) to search in inorder[].

So, In worst case time complexity will be O(n^2).

Auxiliary Space Used:

O(n).

As we are constructing the binary tree and storing values in treenodes. Every node will take constant space to store value and addresses for left and right treenode. So, it will be O(n).

Space Complexity:

O(n).

As input is O(n) and auxiliary space used is also O(n).

So, O(n) + O(n) -> O(n).


// -------- START --------

    static int current_index;
    
    public static TreeNode constructBinaryTree(int inorder[], int preorder[]) {
        
        int arr_len = inorder.length;
        
        current_index = 0;
        
        return utilConstructBinaryTree(inorder, preorder, 0, arr_len - 1);
        
    }
    
        /* Recursive function to construct a binary tree using Inorder traversal 'inorder[]'
        and Preorder traversal 'preorder[]'. Initial value of 'start' and 'end' should be '0' 
        and 'arr_len-1'*/
    
       // Initially 'current_index' should be '0'.

    /* Here, 'start' and 'end' values indicate search range in 'inorder[]' for value at index 
          'current_index' of 'preorder[]'.*/

    // Create 'root' node of value at index 'current_index' of 'preorder[]'.

    /* If value found at index 'x' in 'inorder[]', it means values of range [start, x] of 'inorder[]' will 
        lie in left subtree of root node and values of range [x, end] of 'inorder[]' will lie 
        in right subtree of root node.*/


    public static TreeNode utilConstructBinaryTree(int inorder[], int preorder[], int start, int end) {


        if(start>end)
            return null;
        
        /* Pick current node from Preorder traversal using current_index 
            and increment current_index */
        
        TreeNode root = new TreeNode(preorder[current_index++]);

        /* If above node has no children then return */
        
        if(start == end) {
            return root;
        }
        
        /* Else find the index of this node in Inorder traversal */
        
        int index_of_inorder = findIndex(inorder, root.value, start, end);
        
        /* Using index in Inorder traversal, construct left and 
            right subtrees */
        
        root.left = utilConstructBinaryTree(inorder, preorder, start, index_of_inorder - 1);
        root.right = utilConstructBinaryTree(inorder, preorder, index_of_inorder + 1, end);
        
        return root;
    }
    
    /* This function is to search 'value' in 'inorder' in the range [start, end] and 
       returns index of that 'value'. */
    
    public static int findIndex(int inorder[], int value, int start, int end) {
        
        while(start<=end) {
            
            if(inorder[start] == value) {
                return start;
            }
            
            start++;
        }
        
        return -1;
        
    }
    
    // -------- END --------

2) optimal_solution.java

Time Complexity:

O(n).

We are using hashmap to search index of value in inorder[], and hashmap takes O(1) time (search in hash map can be upto O(n) in worst case, when values are in wide range and carefullly chosen) to search value. So, in every case time complexity will be O(n).

Auxiliary Space Used:

O(n).

As we are constructing binary tree and storing value in treenode, so every node will take constant space to store value and addresses for left and right treenode. Here, we are using hashmap to store inorder[] values with index and it will take O(n) space to store <value,index> pair. So, Auxiliary space will be O(n) + O(n) -> O(n).</value,index>

Space Compelxity:

O(n).

As input is O(n) and auxiliary space used is also O(n).

So, O(n) + O(n) -> O(n).


// -------- START --------
    
    static int current_index;

    
    public static TreeNode constructBinaryTree(int inorder[], int preorder[]) {

        int arr_len = inorder.length;
        
        /* HashMap to store values of 'inorder[]' with index. So, here key and value pair 
            of hashmap will be value and index pair of 'inorder[]'. */
        
        HashMap value_hash_inorder = new HashMap();
        
        // Storing value and index pair of 'inorder[]' in hashmap.

        for(int i = 0 ; i value_hash_inorder) {

        if(start>end)
            return null;

        /* Pick current node from Preorder traversal using current_index 
        and increment current_index */
        
        TreeNode root = new TreeNode(preorder[current_index++]);
        
        /* If above node has no children then return */

        if(start == end) {
            return root;
        }

        /* Else find the index of this node in Inorder traversal */
        int index_of_inorder = value_hash_inorder.get(root.value);
        
        root.left = utilConstructBinaryTree(
                inorder, preorder, start, index_of_inorder - 1, value_hash_inorder);
        root.right = utilConstructBinaryTree(
                inorder, preorder, index_of_inorder + 1, end, value_hash_inorder);

        return root;
    }
    
    // -------- END --------

Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts