v9.1.1
Menu

Construct Binary Tree from Preorder and Inorder

mediumPROTrees & GraphsMicrosoft DSA

Given preorder and inorder traversal arrays, construct the binary tree.

Output the level-order traversal of the constructed tree, space-separated.

Example

Input
3,9,20,15,7
9,3,15,20,7
Output
3 9 20 null null 15 7
Reasoning
  • The preorder traversal array [3, 9, 20, 15, 7] represents the order in which nodes are visited: root, left subtree, right subtree. The first element 3 is the root node.
  • The inorder traversal array [9, 3, 15, 20, 7] represents the order in which nodes are visited: left subtree, root, right subtree. This helps to identify the left and right child nodes of the root 3, which are 9 and 20 respectively.
  • The left subtree of 3 only contains 9, and the right subtree of 3 is constructed from the remaining elements [15, 20, 7] in the inorder array, with 20 as the root, 15 as its left child, and 7 as its right child.
  • The constructed binary tree is then traversed level-by-level to produce the output: 3 (root), 9 (left child of 3), 20 (right child of 3), null (no left child of 9), null (no right child of 9), 15 (left child of 20), 7 (right child of 20).

Constraints

  • 1 <= len(preorder) == len(inorder) <= 3000
  • All values are unique

More from Microsoft DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.