:orphan:

Construct Binary Tree from Preorder and Inorder Traversal
=========================================================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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*.

 

**Example 1:**

|image1|

::


   Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
   Output: [3,9,20,null,null,15,7]

**Example 2:**

::


   Input: preorder = [-1], inorder = [-1]
   Output: [-1]

 

**Constraints:**

- ``1 <= preorder.length <= 3000``
- ``inorder.length == preorder.length``
- ``-3000 <= preorder[i], inorder[i] <= 3000``
- ``preorder`` and ``inorder`` consist of **unique** values.
- Each value of ``inorder`` also appears in ``preorder``.
- ``preorder`` is **guaranteed** to be the preorder traversal of the
  tree.
- ``inorder`` is **guaranteed** to be the inorder traversal of the tree.

.. |image1| image:: https://assets.leetcode.com/uploads/2021/02/19/tree.jpg

.. highlight:: python

Pattern
-------
Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Solution
--------
Since preorder traversal prints the root node first, we extract the value
``val`` of the root node from the tip of ``preorder``. The same value ``val``
divides ``inorder`` into two parts: the left subtree and the right subtree. We
can then recursively build the left subtree by using the rest of the
``preorder`` and the left half of ``inorder``. Once the left subtree is built,
we build the right subtree by using the rest of the ``preorder`` from buliding
the left subtree and the right half of ``inorder``.

Code
----

.. literalinclude:: ../problems/medium/construct-binary-tree-from-preorder-and-inorder-traversal/construct_binary_tree_from_preorder_and_inorder_traversal__approach_1.py
    :language: python
    :lines: 19-

Test
----
>>> from construct_binary_tree_from_preorder_and_inorder_traversal__approach_1 import buildTree
>>> preorder = [3, 9, 20, 15, 7]
>>> inorder = [9, 3, 15, 20, 7]
>>> root = buildTree(preorder, inorder)
>>> root.preorder()
[3, 9, 20, 15, 7]
>>> root.inorder()
[9, 3, 15, 20, 7]
>>> preorder = [-1]
>>> inorder = [-1]
>>> root = buildTree(preorder, inorder)
>>> root.preorder()
[-1]
>>> root.inorder()
[-1]

Complexity
----------
| :math:`n` is the number of nodes in the binary tree
| Time: :math:`O(n^2)` — finding index of element in array per recursive call
| Auxiliary Space: :math:`O(1)` — we only slice and pass references to the input arrays

.. autoclass:: construct_binary_tree_from_preorder_and_inorder_traversal__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: construct_binary_tree_from_preorder_and_inorder_traversal__approach_1.buildTree

.. autofunction:: construct_binary_tree_from_preorder_and_inorder_traversal__approach_1.build_tree