Construct Binary Tree from Inorder and Preorder
Hard Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Constructing a Unique Binary Tree from Preorder and Inorder Traversals, Binary Tree, Tree Construction, Preorder Traversal, In-order Traversal, Tree Traversal, Recursion, Hash Map, Time Complexity, Space Complexity, Pointer, inorder traversal, space complexity, divide and conquer, binary tree, hash map operations, tree construction, preorder traversal, time complexity analysis, tree traversal, Construct Tree from Traversals.
Problem Statement: Given the preorder and inorder traversals of a unique binary tree, reconstruct and return the root of the binary tree. It is guaranteed that an answer exists and that the inorder and preorder traversals describe a unique binary tree. Input Specification: Two integer arrays, preorder and inorder, representing the preorder and inorder traversal of the binary tree, respectively. Output Specification: Return the root node of the constructed binary tree. Example 1: Input: inorder = [40, 20, 50, 10, 60, 30] preorder = [10, 20, 40, 50, 30, 60] Output: (The unique Binary Tree constructed from these traversals, which has inorder traversal: [40, 20, 50, 10, 60, 30] and preorder traversal: [10, 20, 40, 50, 30, 60]) Example 2: Input: inorder = [9, 3, 15, 20, 7] preorder = [3, 9, 20, 15, 7] Output: (The unique Binary Tree constructed from these traversals, which has inorder traversal: [9, 3, 15, 20, 7] and preorder traversal: [3, 9, 20, 15, 7])