Feature #9: Recreating the Decision Tree

Implement the "Recreating Decision Tree" feature for our "Facebook" project.

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:

Binary tree for given traversals

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:

Dividing the decision tree into two subtrees

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

Preorder traversal of the tree

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 to ...

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.