Given two integer arrays preorder
and inorder
where preorder
is the preorder traversal of a binary tree and inorder
is the inorder traversal of the same tree, construct and return the binary tree.
Reminder: BST property
Solution using preorder inorder and recursion
- Inorder is nothing but LEFT ROOT RIGHT Traversal
- Preorder is nothing but ROOT LEFT RIGHT Traversal
- Find the root (the first element in preorder) in inorder –> the element on the right side are the right side of the tree, the elements on the left are the left side of the tree.
- Recursion with sub-preorders and sub-inorders