Construct tree from inorder & postorder
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal – Given the inorder and postorder traversal arrays of a binary tree, construct and return the binary tree.
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
Quick Answer: This question evaluates understanding of binary tree reconstruction and traversal order relationships, specifically the ability to derive tree structure from inorder and postorder arrays and implement the corresponding algorithm.
Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return the binary tree.
Because a `TreeNode` cannot be returned directly here, return the tree as its **level-order (breadth-first) array representation** using LeetCode's convention: list values level by level, use `null`/`None` for missing children, and trim any trailing `null`s. For an empty tree return an empty list.
For example, with `inorder = [9,3,15,20,7]` and `postorder = [9,15,7,20,3]`, the reconstructed tree is:
```
3
/ \
9 20
/ \
15 7
```
which serializes to `[3, 9, 20, null, null, 15, 7]`.
Key idea: the **last** element of `postorder` is always the root. Locate that root inside `inorder` to split the left and right subtrees, then recurse. Consuming `postorder` from the right (root, then right subtree, then left subtree) lets you build the tree in a single pass with an index map for O(1) root lookups.
Constraints
- 1 <= inorder.length <= 3000 (and postorder.length == inorder.length)
- -3000 <= node values <= 3000
- inorder and postorder consist of unique values
- Each value of postorder also appears in inorder
- inorder is guaranteed to be the inorder traversal of the tree
- postorder is guaranteed to be the postorder traversal of the tree
Examples
Input: ([9,3,15,20,7], [9,15,7,20,3])
Expected Output: [3, 9, 20, None, None, 15, 7]
Explanation: Root is the last postorder element 3; it splits inorder into left=[9] and right=[15,20,7]. The resulting tree serializes level-order to [3, 9, 20, null, null, 15, 7].
Input: ([-1], [-1])
Expected Output: [-1]
Explanation: Single node with a negative value; the tree is just the root -1.
Hints
- The last element of postorder is always the root of the (sub)tree. Find it inside inorder to know how many nodes are in the left vs. right subtree.
- Build a value -> index hash map over inorder once so each root lookup is O(1) instead of an O(n) scan.
- Consume postorder from the right end: pop the root, then recursively build the RIGHT subtree before the LEFT, because that matches the reverse-postorder order (root, right, left).
- After building the tree, run a BFS that pushes both children (even null ones) so the output matches LeetCode's level-order format, then trim trailing nulls.