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.

Reconstruct tree from inorder and postorder

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given two arrays representing the inorder and postorder traversals of a binary tree with unique values, reconstruct the original binary tree and return its root node. Implement a recursive solution, clearly defining base cases such as empty ranges. Analyze the time and space complexity. If you choose array slicing, explain its impact on complexity; alternatively, implement an index-range approach using a value-to-index map to achieve linear time.

Quick Answer: This question evaluates understanding of binary tree traversal relationships, recursive construction techniques, and algorithmic time and space complexity, reflecting core data structures and recursion competencies.

Given two integer arrays `inorder` and `postorder` representing the inorder and postorder traversals of a binary tree with **unique** node values, reconstruct the tree and return a level-order serialization of it. Return the tree as a list produced by a breadth-first (level-order) walk: visit nodes left-to-right level by level, appending each node's value, and appending `null`/`None` for each missing child of a visited node. Trim trailing `null` values. (For example, the tree ``` 3 / \ 9 20 / \ 15 7 ``` serializes to `[3, 9, 20, null, null, 15, 7]`.) The last element of `postorder` is always the root. Locate the root in `inorder`: everything to its left forms the left subtree, everything to its right forms the right subtree. Recurse, consuming `postorder` from the back (right subtree before left subtree, since postorder is left-right-root reversed). Implement a recursive solution with a clear base case for empty ranges. Prefer the **index-range + value-to-index map** approach for O(n) time over repeated array slicing (which makes the build O(n^2) due to per-call copying and re-searching).

Constraints

0 <= len(inorder) == len(postorder)
All node values are unique
postorder is a valid postorder traversal of the same tree described by inorder
Node values fit in a signed 32-bit integer (may be negative)

Examples

Input: ([9, 3, 15, 20, 7], [9, 15, 7, 20, 3])

Expected Output: [3, 9, 20, None, None, 15, 7]

Explanation: Classic example: root 3 (last of postorder); 9 is its left child, 20 its right; 20 has children 15 and 7.

Input: ([], [])

Expected Output: []

Explanation: Empty traversals reconstruct the empty tree (base case lo > hi at the top level).

Input: ([1], [1])

Expected Output: [1]

Explanation: Single node: the root has no children, so trailing Nones are trimmed.

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

Expected Output: [1, 2]

Explanation: Left-skewed: inorder [2,1] with root 1 (last of postorder) puts 2 entirely to the left -> 1 with left child 2.

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

Expected Output: [1, None, 2]

Explanation: Right-skewed: root 1 has an empty left subtree (None) and right child 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: Perfectly balanced tree of 7 nodes; root 1 with subtrees rooted at 2 and 3.

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

Expected Output: [-1, -3, -2]

Explanation: Negative values: root -1 with left child -3 and right child -2.

Hints

The last element of postorder is the root of the (sub)tree. Find it in inorder to split into left and right subtrees.
Consume postorder from the back. Because postorder ends with the root and the right subtree's nodes come just before it, build the RIGHT subtree before the LEFT one when popping from the end.
Precompute a value-to-index map over inorder so each root lookup is O(1) — this turns the O(n^2) slicing approach into O(n). Use index ranges (lo, hi) instead of copying subarrays.
Your base case is an empty range (lo > hi), which returns no node — this naturally handles leaves and the empty tree.

Quick Overview

This question evaluates understanding of binary tree traversal relationships, recursive construction techniques, and algorithmic time and space complexity, reflecting core data structures and recursion competencies.