[Tree Serialization] Construct Binary Tree from Preorder and Inorder Traversal

[sudosf]

Problem

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

References

• LeetCode: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
• GFG: https://www.geeksforgeeks.org/problems/construct-tree-1/1
• Sheet: https://www.risingbrain.org/sheet#tree (Serialization [Two Pointer] Move Zeroes #4)
• Parent: Pattern: Tree - Serialization and Construction #114

Difficulty

🟡 Medium

Companies

Amazon, Microsoft, Google

Notes

Language: Java
Preorder first element is always root. Find root in inorder to split left/right subtrees. Use a HashMap for O(1) inorder lookups.