Prerequisites: Binary trees, Binary tree traversal techniques.
Problem: Construct and return a binary tree using two integer arrays, preorder and inorder. The preorder array represents the preorder traversal of the binary tree, while the inorder array represents the inorder traversal of the same tree.
Solution Approach:
We need to understand preorder and postorder traversal first, and then go ahead.
Basic idea is:
preorder[0] is the root node of the tree.
preorder[x] is a root node of a sub tree.
In inorder traversal:
When inorder[index] is an item in the inorder traversal,
inorder[0]-inorder[index-1] are on the left subtree.
inorder[index+1]-inorder[size()-1] are on the right subtree.
if there is nothing on the left, that means the left child of the node is NULL
if there is nothing on the right, that means the right child of the node is NULL
Algorithm:
-
Start from rootIdx 0
-
Find preorder[rootIdx] from inorder, let’s call the index pivot
-
Create a new node with inorder[pivot]
-
Create its left child recursively
-
Create its right child recursively
-
return the created node.
Time complexity: O(N), as we need to iterate through each element of inorder and recursively
create the tree for each node as some subtree.
Space complexity: O(N), as creation for each node shall take O(N) space.