Daily bit(e) of C++ | Construct a binary tree from preorder and inorder traversals
Daily bit(e) of C++ #289, Common interview problem: Construct a binary tree from preorder and inorder traversals.
Today, we will look at a common C++ interview problem: Construct a binary tree from preorder and inorder traversals.
Given the preorder and inorder traversals (both as std::span<int>), construct the corresponding binary tree.
Use the add_node(int) method on the provided tree object and return the root node.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/Y4WoE3ETY.
Solution
Pre-order traversal immediately gives us the root of the tree. The following elements belong to the left and right subtrees. The one piece of information we are missing is how many elements belong to the left subtree and how many belong to the right subtree.
However, this number of nodes is easily obtainable from the in-order traversal, where the node creates a partition. All elements to the left belong to the left subtree, and all elements to the right belong to the right subtree.
Putting this together, we can iterate over the preorder traversal, keeping track of the relevant partition of inorder traversal as we recurse in the tree.
