How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at NVIDIA.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at NVIDIA during technical interviews.

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.

Input: ([], [])

Expected Output: []

Explanation: Empty traversals produce an empty tree, serialized as [].

Input: ([2,1], [2,1])

Expected Output: [1, 2]

Explanation: Root is 1 (last of postorder). In inorder, 2 comes before 1, so 2 is the left child: tree is 1 with left child 2 -> [1, 2].

Input: ([1,2], [2,1])

Expected Output: [1, None, 2]

Explanation: Root is 1; in inorder, 2 comes after 1, so 2 is the right child. Level-order is [1, null, 2].

Input: ([4,2,5,1,6,3,7], [4,5,2,6,7,3,1])

Expected Output: [1, 2, 3, 4, 5, 6, 7]

Explanation: A full, balanced 7-node tree rooted at 1 with subtrees 2(4,5) and 3(6,7); its level-order serialization is [1,2,3,4,5,6,7].

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.

Quick Overview

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.