Feature #9: Recreating the Decision Tree

Description

Facebook uses a recommendation system to recommend ads to its users. This recommendation system recommends ads on the basis of the results obtained from this decision tree. Facebook wants to implement this recommendation system for Instagram users as well. For this purpose, Facebook wants to replicate the decision tree from a Facebook server to an Instagram server.

The decision tree used in Facebook’s recommendation server is serialized in the form of its inorder and preorder traversals as strings. Using these traversals, we need to create a decision tree for Instagram’s recommendation system.

Let us say we have these preorder and inorder traversals respectively: ["subject", "viewed", "likeable", "notlikeable", "notviewed", "similar", "nonsimilar"] and ["likeable", "viewed", "notlikeable, "subject", "similar", "notviewed", "nonsimilar" ]. The decision tree for these traversals is shown in the illustration below:

Solution

A binary tree is a root node that comes along with its two subtrees, the left subtree and the right subtree. Each subtree is a binary tree itself.

Let us look at the inorder traversal of the tree mentioned above and try to find this structure:

Now, let us look at the preorder traversal of the tree given above:

use the structure of these two traversals to reconstruct the corresponding binary tree. We will search for the root in the preorder traversal, and then we will use this root to search for the left and right subtree in the inorder traversal. We will keep making a recursive call until the tree has been constructed.

Let us try ...