DEV Community is a community of 668,514 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

Solution: Construct Binary Tree from Preorder and Inorder Traversal

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・5 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Examples:

Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Visual:
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.

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

For this solution, we can take advantage of the order of nodes in the preorder and inorder traversals. A preorder traversal is [node, left, right] while an inorder traversal is [left, node, right].

We know that the root node for a tree is the first element of the preorder array (P). We also know that every element to the left of the root element in the inorder array (I) is on the left subtree, and everything to the right of the root element in I is on the right subtree.

Since we know the length of the left and right subtrees by finding the root in I, and since we know the order of the left and right subtrees in P, we can use that to determine the location of the root node in P for each of the two subtrees.

With this information, we can define a recursive helper function (splitTree) that will split the tree into two and then recursively do the same for each subtree.

In order to make this work, we just need to pass left and right limits (ileft, iright) defining the subarray of the current subtree in I, as well as the index (pix) of the root node of the subtree in P.

At this point, we could iterate forward through I until we found out the location (imid) of the root node each time, but that would push this solution to a time complexity of O(N^2).

Instead, we can make a prelimanary index map (M) of the values in I, so that we can look up the value for imid in O(1) time in each recursion. This will lower the time complexity to O(N) at the cost of a space complexity of O(N).

In the example in the graphic above, where P = [8,2,7,1,9,3,6] and I = [7,2,1,8,3,9,6], the root would be 8, so we know that imid (its location in I) is 3, and since we still are using the full array, ileft = 0 and iright = I.length-1, or 6. This means that the left subtree is imid - ileft = 3 elements long ([7,2,1] to the left of 8 in I) and the right subtree is iright - imid = 3 elements long ([3,9,6] to the right of 8 in I).

We can apply those dimensions from I to figure out the ranges of those subtrees in P, as well. The left subtree will start right after the root in P (pix + 1), and the right subtree will start once the left subtree ends (pix + 1 + (imid - ileft).

At each recursion, if imid = ileft, then there are no nodes in the left subtree, so we shouldn't call a recursion for that side. The same applies to the right side if imid = iright.

• Time Complexity: O(N) where N is the length of P and I
• Space Complexity: O(N) for M

Javascript Code:

(Jump to: Problem Description || Solution Idea)

``````var buildTree = function(P, I) {
let M = new Map()
for (let i = 0; i < I.length; i++)
M.set(I[i], i)
return splitTree(P, M, 0, 0, I.length-1)
};

var splitTree = function(P, M, pix, ileft, iright) {
let rval = P[pix],
root = new TreeNode(rval),
imid = M.get(rval)
if (imid > ileft)
root.left = splitTree(P, M, pix+1, ileft, imid-1)
if (imid < iright)
root.right = splitTree(P, M, pix+imid-ileft+1, imid+1, iright)
return root
}
``````

Python Code:

(Jump to: Problem Description || Solution Idea)

``````class Solution:
def buildTree(self, P: List[int], I: List[int]) -> TreeNode:
M = {I[i]: i for i in range(len(I))}
return self.splitTree(P, M, 0, 0, len(P)-1)

def splitTree(self, P: List[int], M: dict, pix: int, ileft: int, iright: int) -> TreeNode:
rval = P[pix]
root, imid = TreeNode(rval), M[rval]
if imid > ileft:
root.left = self.splitTree(P, M, pix+1, ileft, imid-1)
if imid < iright:
root.right = self.splitTree(P, M, pix+imid-ileft+1, imid+1, iright)
return root
``````

Java Code:

(Jump to: Problem Description || Solution Idea)

``````class Solution {
public TreeNode buildTree(int[] P, int[] I) {
Map<Integer, Integer> M = new HashMap<>();
for (int i = 0; i < I.length; i++)
M.put(I[i], i);
return splitTree(P, M, 0, 0, I.length-1);
}

private TreeNode splitTree(int[] P, Map<Integer, Integer> M, int pix, int ileft, int iright) {
int rval = P[pix], imid = M.get(rval);
TreeNode root = new TreeNode(rval);
if (imid > ileft)
root.left = splitTree(P, M, pix+1, ileft, imid-1);
if (imid < iright)
root.right = splitTree(P, M, pix+imid-ileft+1, imid+1, iright);
return root;
}
}
``````

C++ Code:

(Jump to: Problem Description || Solution Idea)

``````class Solution {
public:
TreeNode* buildTree(vector<int>& P, vector<int>& I) {
unordered_map<int, int> M;
for (int i = 0; i < I.size(); i++)
M[I[i]] = i;
return splitTree(P, M, 0, 0, I.size()-1);
}

private:
TreeNode* splitTree(vector<int>& P, unordered_map<int, int>& M, int pix, int ileft, int iright) {
int rval = P[pix], imid = M[rval];
TreeNode* root = new TreeNode(rval);
if (imid > ileft)
root->left = splitTree(P, M, pix+1, ileft, imid-1);
if (imid < iright)
root->right = splitTree(P, M, pix+imid-ileft+1, imid+1, iright);
return root;
}
};
``````
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}