Solve it using C++.
You will build a simple binary tree data structure from somearbitrary input and also the “crawler” function that will locatedata
inside of it. 1. Build a class Node. It should have a value thatit stores and also links to its parent and children (if theyexist). Build
getters and setters for it (e.g. parent node, child node(s)). 2.Write a method build_tree which takes an array of data (e.g. [1, 7,4,
23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]) and turns it into abinary tree full of Node objects appropriately placed. Start byassuming
the array you get is sorted. 3. Now refactor your build_tree tohandle data that isn’t presorted and cannot be easily sorted priorto
building the tree. You’ll need to figure out how to add a nodefor each of the possible cases (e.g. if it’s a leaf versus in themiddle
somewhere). 4. Write a simple script that runs build_tree so youcan test it out. 5. Build a method breadth_first_search which
takes a target value and returns the node at which it is locatedusing the breadth first search technique.
[Tip: You will want to use an array acting as a queue to keep trackof all the child nodes that you have yet to search and to add
new ones to the list. If the target node value is not located,return nil.]
6. Build a method depth_first_search which returns the node atwhich the target value is located
using the depth first search technique. Use an array acting as astack to do this. 7. Next, build a new method dfs_rec whichruns
a depth first search as before but this time,
instead of using a stack, make this method recursive.
[Tip: 1. You can think of the `dfs_rec` method as alittle robot that crawls down the tree, checking if a node is thecorrect node
and spawning other little robots to keep searching
the tree. No robot is allowed to turn on, though, until all therobots to its left have finished their task. 2. The method willneed to
take in both the target value and the current node to compareagainst.