LeetCode Meditations: Construct Binary Tree from Preorder and Inorder Traversal
Let's look at the description for this problem:
Given two integer arrays
preorderandinorderwherepreorderis the preorder traversal of a binary tree andinorderis the inorder traversal of the same tree, construct and return the binary tree.
For example:
Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
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 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:
let root = new TreeNode(preorder[0]);
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):
The preorder array in this case would be this:
[8, 3, 1, 6, 4, 7, 10, 14, 13]
[8, 3, 1, 6, 4, 7, 10, 14, 13]
And, inorder would look like this:
[1, 3, 4, 6, 7, 8, 10, 13, 14]
[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: [8, 3, 1, 6, 4, 7, 10, 14, 13]
inorder: [1, 3, 4, 6, 7, 8, 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, 3, 1, 6, 4, 7, 10, 14, 13] | [8, 3, 1, 6, 4, 7, 10, 14, 13] |
| inorder | [1, 3, 4, 6, 7, 8, 10, 13, 14] | [1, 3, 4, 6, 7, 8, 10, 13, 14] |
We can then slice the arrays to get the subtrees:
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);
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);
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:
if (preorder.length === 0 || inorder.length === 0) {
return null;
}
if (preorder.length === 0 || inorder.length === 0) {
return null;
}
And, here's the final solution in TypeScript:
/**
* 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;
}
/**
* 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, as well as finding the index. So, the overall time complexity is . The space complexity is in the worst case—I think— as well because we create the slices in each recursive call which in the worst case can have depth.
The explanation of this approach can also be found in NeetCode's video.
Next up, we'll look at the problem called Binary Tree Maximum Path Sum. Until then, happy coding.