LeetCode Meditations: Construct Binary Tree from Preorder and Inorder Traversal
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-04-30 19:43:49

Let's look at the description for [this 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_.

For example:

<img src="https://assets.leetcode.com/uploads/2021/02/19/tree.jpg" alt="Example image 1" />

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

---

Even though it has a medium difficulty label, I think this one can be quite challenging.

So, let's start with what we know.

We know that a [preorder traversal](https://rivea0.github.io/blog/leetcode-meditations-chapter-7-trees#preorder) first looks at the root node, then goes to the left subtree, then the right subtree.

To construct any tree, first of all, we need to start with the root. Here, we can do it easily like this:

```ts
let root = new TreeNode(preorder[0]);
```

And, now?

We need to add the left and right children of the root somehow. 
One idea is that we can get them recursively by partitioning the arrays. Let's look at this binary tree (which is also a [binary search tree](https://rivea0.github.io/blog/leetcode-meditations-chapter-7-trees#bst)):

<img src="https://rivea0.github.io/blog/post-images/2024-04-15/bst-example1.png" width="50%"/>

The `preorder` array in this case would be this:

```ts
[8, 3, 1, 6, 4, 7, 10, 14, 13]
```

And, `inorder` would look like this:

```ts
[1, 3, 4, 6, 7, 8, 10, 13, 14]
```

What we know about the `inorder` array is that _**all the values to the left of the root are in the left subtree**_. And, _**all the values to the right of the root are in the right subtree**_.
Remember that inorder traversal gets all the nodes in the left subtree first, then the root. Preorder traversal, however, gets the root first, then all the nodes in the left subtree.

Therefore, _the nodes in the left subtree + the root node_ will be the in the same portion in both of the arrays:

`preorder`: \[<mark>8, 3, 1, 6, 4, 7</mark>, 10, 14, 13\]

`inorder`: \[<mark>1, 3, 4, 6, 7, 8</mark>, 10, 13, 14\]

If we get the root node's index in the `inorder` array, we can easily get the left subtree in the `preorder` array as well. The rest will be the right subtree:

|              | left subtree                         | right subtree                        |
| ------------ | ------------------------------------ | ------------------------------------ |
| **preorder** | \[8, <mark>3, 1, 6, 4, 7</mark>, 10, 14, 13\] | \[8, 3, 1, 6, 4, 7, <mark>10, 14, 13</mark>\] |
| **inorder**  | \[<mark>1, 3, 4, 6, 7</mark>, 8, 10, 13, 14\] | \[1, 3, 4, 6, 7, 8, <mark>10, 13, 14</mark>\] |

We can then slice the arrays to get the subtrees:

```ts
let rootIdx = inorder.findIndex(i => i === root.val);

let preorderLeft = preorder.slice(1, rootIdx + 1);
let inorderLeft = inorder.slice(0, rootIdx);
let preorderRight = preorder.slice(rootIdx + 1, preorder.length);
let inorderRight = inorder.slice(rootIdx + 1, inorder.length);
```

| Note |
| :-- |
| One of the constraints in the problem says: <br /> <br /> _`preorder` and `inorder` consist of unique values._ <br /> <br /> So we'll always get the correct index. |

Now that we know where the subtrees reside, we can build our tree recursively.

Our base case is when one of the arrays is empty:

```ts
if (preorder.length === 0 || inorder.length === 0) {
  return null;
}
```

And, here's the final solution in TypeScript:

```ts
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  if (preorder.length === 0 || inorder.length === 0) {
    return null;
  }

  let root = new TreeNode(preorder[0]);
  let rootIdx = inorder.findIndex(i => i === root.val);

  // Get the left and right subtrees in preorder and inorder arrays
  let preorderLeft = preorder.slice(1, rootIdx + 1);
  let inorderLeft = inorder.slice(0, rootIdx);
  let preorderRight = preorder.slice(rootIdx + 1, preorder.length);
  let inorderRight = inorder.slice(rootIdx + 1, inorder.length);

  root.left = buildTree(preorderLeft, inorderLeft);
  root.right = buildTree(preorderRight, inorderRight);

  return root;
}
```

#### Time and space complexity

For each node that we calculate the index of, we also slice the arrays. [Slicing itself is an O(n) operation](https://stackoverflow.com/a/72545403), as well as finding the index. So, the overall time complexity is {% katex inline %} O(n^2) {% endkatex %}. The space complexity is in the worst case—_I think_—{% katex inline %} O(n^2) {% endkatex %} as well because we create the slices in each recursive call which in the worst case can have {% katex inline %} O(n) {% endkatex %} depth.

---

The explanation of this approach can also be found in [NeetCode's video](https://www.youtube.com/watch?v=ihj4IQGZ2zc). 

Next up, we'll look at the problem called [Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum). Until then, happy coding.