Construct a Binary Tree from given Inorder and Preorder traversals

Posted by N.K. Chauhan on Jan 19, 2023

Given two arrays representing In-order and Preorder traversals of a binary tree, the task is to construct the tree and print "level-order" traversal.

Example 1: Construct Binary Tree from Preorder and In-order Traversal

Input : Inorder: 2,1,3, Pre-order: 1,2,3

Output : 1,2,3

           1
          / \
         2   3

Example 2: Construct Binary Tree from Preorder and In-order Traversal

Input : Inorder: 4,2,5,1,3,6, Pre-order: 1,2,4,5,3,6

Output : 1,2,3,4,5,6

           1
         /   \
        2     3
       / \   / 
      4   5 6   


Solutions

Method 1: Recursion

In a Preorder traversal, the left-most element is the root of the tree.

By searching "root" in the Inorder traversal, we can find out all elements on the left side of "root" is in the left subtree and elements on right in the right subtree.

We recursively follow the above steps and construct the final tree.

preOrderIndex -> 0

constructTree(int[] inOrder, int[] preOrder, int inStart, int inEnd)
	if (inStart > inEnd)
    		return null
	node -> new Node(preOrder[preOrderIndex++])
	if (inStart == inEnd)
    		return node
	divideIndex -> search(inOrder, inStart, inEnd, node.data)
	node.left -> constructTree(inOrder, preOrder, inStart, divideIndex - 1)
	node.right -> constructTree(inOrder, preOrder, divideIndex + 1, inEnd)
	return node

search(int arr[], int start, int end, int value)
    i 
    for (i = start; i <= end; i++)
        if (arr[i] == value)
            return i
    return i

Complexity
The time complexity of this solution is O(n2) and space complexity is O(n) due to auxiliary stack.

Related


Check if a binary tree is subtree of another binary tree

Post-order Tree Traversal - Iterative and Recursive

Construct a binary tree from a string consisting of parenthesis and integers

Check if two binary trees are a mirror image of each other

Sum of nodes on the longest path from root to leaf node

Print diagonal traversal of a binary tree

Print/Traverse a Binary Tree in Zigzag Order

Print Nodes in Top View of a Binary Tree

Check if a binary tree has all leaf nodes at same level

Check if a given binary tree is Sum Tree