Everybody has to go and this is Caleb with Deb's slopes dot com and in this video we're going to be
talking about the data structure called the tree.
OK.
And we're going to learn how to build one in swift which is pretty awesome.
So I'm going to first pull open a diagram to show you what a tree looks like visualized.
And then we're going to dive into actually creating one.
So here is how a tree is organized and if you're thinking this looks a lot like a family tree the data
in a family tree is actually stored in pretty much the same exact way whereas you would have one family
here your mom and dad and then maybe their children.
Then this would be you know whomever they married and then their children et cetera et cetera going
all the way down the family tree starting you know way back when in some other country perhaps or maybe
you've been in the same country the whole time.
Who knows anyway.
So at the very top of our tree we have what is called the root.
OK.
And this is something that is applicable this or I guess we should say the data stored in the root is
data that is applicable to all of the nodes below it.
So the root note here is devices we're going to be using this tree to store different kinds of devices.
And what I have done is I've branched off from my route and created some notes.
Now the route we can call it the root node because it also is a node.
But we're going to call it the root because it is unique in the fact that it is the very top of our
chart where everything starts.
So the first node over here on the left is Apple.
So Apple devices.
And then on the right we have a robot that will be Android devices but they're both devices right and
so that's why the route here can relate to all of the other things in the tree.
So they're all going to be devices.
Now the Apple node we're going to call it a node that's kind of like a child in a heap.
Right.
It is a child of this parent root node.
So this node is for Apple devices.
OK.
And if we branch off of Apple devices we have an iPhone and a MacBook.
Now obviously there are many more Apple devices but just for this example I just used to.
And so then if we branch off of the iPhone node we can see there is iPhone 10 iPhone 8 iPhone for us
and we could go on and on and on and on and on.
Alternatively on the Android side there are two nodes here one is for the Samsung Galaxy S 9 and the
other is for some random Android tablet.
There are too many to actually differentiate.
So you're seeing the word leaf over here and a leaf is a node that does not have any children nodes
so in this diagram the MacBook the Samsung Galaxy S 9 and this Android tablet are all examples of leaves
because they have no children nodes that come off of them.
Now we could go into greater detail in our tree here or we could go into the iPhone 10 and we could
split you know a child node for the battery life we could split a child node off for the screen resolution
etc etc. and we can dive into all of those specific details for all of those devices.
The tree can just continue to grow and get increasingly complex with each level down the tree.
But I think we should actually start to make one.
So pull up an X code like Sue and get started with a new playground.
Of course it goes to the wrong window anyway.
So create a blank blank playground that can't even speak today.
And we're going to go ahead and name this tree free that no just name it something and save it somewhere.
And I'm going to make it full screen so delete everything in here and just import Foundation.
That's what's most important for what we're doing today and we're going to go ahead and begin by creating
a class called node.
And like I said in our diagram here the route also qualifies as a node right because it has children
nodes just like Android has children node.
Apple has children nodes.
The route while it is the very first node.
It's also a node.
So go ahead and create a class called node and give it some curly brackets there to open it up and we're
going to basically first create a variable called value that is going to store the value of whatever
in this node is whether it's the parent node whether it is the child node.
Each node needs a value and it's going to be of type string.
So go ahead and type var value of type string.
All right.
We're going to create an initializer later then we're going to need to create an array called Children
K because our node has the potential to have children.
So go ahead and say our children.
And that's going to be an array of type node and we're going to just initialize it to be an empty array
from the get go.
Now we're going to go ahead and create a variable called Parent x.
It's going to be optional and we're going to use the weak keyword so weak var parent type node and it's
going to be optional because not every node actually has a parent like our root node.
OK we're going to start somewhere.
This no does not have a parent.
So we need to make it optional because it is possible for a node not to have a parent.
However we need to actually provide the option for our nodes to have children so that's why we have
an empty array there so we can add them on very easily.
So now we're going to go ahead and just create an initialiser like so we're going to pass in a value
of type string and we're going to set self-taught value WIPs value to be equal to value.
OK.
So that sets that.
But we want to be able to add a child node to whatever node this is.
And so we're going to add a function here called add.
So type phunk ad and we're going to just say child that's what we're going to call the parameter to
pasan and that's going to be of type note.
All righty.
Now in order to add a child to this node we're going to go ahead and append children pen and we're going
to pass in that child then we're going to need to set the parent of that child.
So to do that we can just call child datt parent Keiko's child of course is of type node.
It has an optional parent.
We're going to set child up parent to be self K because whatever the child is this node whatever instance
of this class will be that is who we're going to set the parent to.
So we're kind of killing two birds with one stone here which is pretty cool.
So we now have a node class and we are now ready to build a tree which is really really cool.
So let's first try to model this actual tree itself by first creating the parent node.
So we're going to just say let devices OK equal node and we're going to just pass in devices as the
value already.
And of course it shows up over here in the print out of type node which is pretty neat.
And now we're going to go ahead and create some child nodes.
So let's go ahead and create.
Let Apple devices equals node and we're going to pass in a value of Apple.
All righty.
Let Android devices equals node and we're going to say Android Android.
OK.
And then all we need to do to add these two devices to our tree is call devices and pass an Apple devices
and then do it again.
Devices don't add and passen Android devices.
So now we're going to see what it looks like when we print it out.
So we're going to print books.
Devices like so and when it prints out check out what we get.
Nothing it just prints out Noad.
So we need to actually set up a way to describe what is in the notes and we're going to actually write
a quick little extension here of node that it conforms to the custom string convertible protocol.
And we're going to create a quick little variable called description of type string but we're going
to set some custom stuff inside so that we can check that or even our children.
OK we're going to first print out the value of maybe the parent note on the top.
The root node and then we're going to go ahead and say hey if the children array is not empty We're
going to cycle through and we're going to add those in but we're going to add some curly brackets so
that we can show the actual layers of the tree like so and so to do that we're going to go ahead and
first create a variable called text.
OK.
And that's going to basically just be whatever the value variable is.
So in the instance of our devices node this string devices is what would print out here so we're setting
text to be devices then we're going to go ahead and say hey if children dot is empty and we want that
to be false.
So we're going to put the exclamation mark there to invert it.
So if Children's is empty is not true meaning if there are children for this particular node we're going
to go ahead and just take text and we're going to do.
Plus equals there to append some text to the end of it and we're going to go ahead and append a space
and a curly bracket so that we can basically describe the first item then we'll put a curly bracket
and then we'll fit in the next set of values and put those inside of a curly bracket.
OK.
And that will basically show the different layers.
You'll see what I mean.
And the second one it actually prints out.
Then we're going to go ahead and add that little you know chunk of a string to children.
And what we're going to do is we're going to call map and K and map is a very cool function.
That's going to allow us to actually iterate over every item in the array and then we're going to join
each of those little items with a comma and a space then we're going to finish it off with brackets
at the end.
You'll see how it'll look in a second.
Let's just do it.
And then look at it and it'll it'll make sense I promise.
So we're going to go ahead and map over every item.
And when you map over each item you can use this temporary variable dollar sign zero or you know whatever
you wanna call it zero dollars broke.
Brooks broke broke Simbel I don't know.
Dollar Signs zero dot and we can actually go ahead and pull out the description of whatever that item
is.
So remember text is going to basically you know get that description.
And once we have that description we can call DOT joined with a separator and that separator is going
to be comma space.
Get rid of the little placeholder there and then after we separate all of the children with a comma
and a space we're going to add another little string which will be a curly bracket to close and a space
and then that is what we will actually set.
So basically we're saying hey we're going to set the value of whatever it is.
So for the devices no devices get set as text.
Then if it doesn't have children this doesn't get called and we can just return that text.
But if there are children we will first show the value so devices then we're going to show its children
by putting them inside of curly brackets separating each one with a comma and then you know that those
two elements are under the device's parent root node.
And so now we have a description.
It's printing out right here at the bottom can you see that we have devices as the root node.
Then below that we have Apple which has one child node an Android which is another child node.
Now I think would be really cool to add in our custom nodes and see how they look.
So let's go ahead and below this we're going to go ahead and type Apple devices dot ad and I'm going
to add in my first group of items which is iPhone and as it prints out you'll see it'll add a new bracket.
So what's the problem.
Ok ok so I forgot if we're going to add in a node we can't just pass in the string because the add function
expects that a node is being passed in so we're going to go ahead and just create a node when we pass
it in and pass in iPhone.
So now when we print it out we'll see that devices has a child called Apple and Apple has a child called
iPhone do you see how this works.
We're basically nesting all of our items.
So obviously it's not as visual like this with know the circles and the lines but if you look at it
it's organized in exactly the same way.
So I'm going to copy and paste this just for time's sake and I'm going to add in a mac book Noad of
course that will update and you see it show up in the print right there.
So cool.
And so now we can start to add nodes to our Android device node.
So Android devices that add we can create a node and pasan maybe galaxy as a node for the Galaxy phones
and then we can copy this and we can just say tablets I guess.
But as you can see when it prints out what we're going to have is devices is the root node.
Below that is Apple and inside Apple there is iPhone and Mac book Inside Android there is Galaxy and
tablets.
Now we can go even further we can say
oh no you know what I just realized we're not going to be able to add nodes to our iPhone node because
we have not actually.
Well we could.
There is a way we could do it.
But I think it's going to be better actually if we.
Yeah let's go ahead and cut this and let's just say let iPhone.
We're going to set that to a node and pass it and we're actually going to be able to work with these
properties and then add value to them.
So let's go ahead and let's cut this node and say let's MacBook equals node and then passen MacBook.
Cool.
And now just for the example I'm going to go ahead and say iPhone ad and I'm going to pass in a note
here for the iPhone 10.
Here we are.
Then I'm going to go ahead and do iPhone add child node and we're going to pass in iPhone 8 and you'll
probably see a printout below you'll see it's doing what it's supposed to do.
But I just think it's really cool how it works.
Noad value.
And I said the iPhone 4 ES I think is for us there we go and we print out the devices you can see that
we have devices under devices we have Apple under apple we have iPhone under iPhone we have iPhone 10
8 and for us then there's MacBook which at this point is a leaf node.
Right.
Because there's no children attached to it.
And then we have Android galaxy and tablet.
So at this point we have faithfully recreated our tree in code which is really neat.
But what good is a tree if we're not able to search for items.
So we're going to go ahead and actually add an extension to our node.
We're going to add some extra functionality to allow us to search for particular node in our tree so
go ahead and type extension node at the bottom and I'm going to make some more space here so we can
actually see what we're doing.
And we're going to write a function that will search our trees.
So go ahead right phunk search and we're going to actually pass in a value of type string and that is
going to actually return the node object which of course is going to be optional because we may not
actually return the node that we are hoping to return.
So go ahead and basically check if the value is equal to self value meaning you know if our instance
of node if we're searching for a value and it's equal to the value that we are you know if we're searching
for devices and the value of the particular node is devices we're just going to go ahead and return
that value.
So return self just like that.
But if that's not the case we're going to go ahead and basically cycle through all the children and
if one is found we will return it.
And if nothing else works we're going to just return nil meaning there is no search result that was
found.
So for child in children remember we're reading an extension so we have access to the children array
and so we can say hey for every child in children if let.
Found equals child search for that value.
OK so we're going to just basically call search upon that child and if that value is found we return
it right.
If that is found We're going to return found wups and then if that doesn't work if all else fails meaning
the search did not end up returning anything we're going to return nil.
Now what we can do is if we want to search a particular portion of our node like let's say I wanted
to search the entire device's node I could create a variable called search result or I guess a constant
and then type devices search and I could search for iPhone and see what happens.
It returns the entire iPhone node.
You see that.
So now I've returned the entire node and now I could go ahead and just say hey.
Search results and maybe if I go in here I could say you know children and print out the first item
in the search result for children and that's going to print out iPhone 10.
Obviously it's optional you'd have to do some work maybe a guard or a way to verify that that value
came back the way you wanted.
But we can now search our tree and pull out an individual node and all of its sub values which is a
really really cool way to do things.
Now I could search devices for iPhone 10 specifically and that's going to actually return the iPhone
10 child right there which is so cool.
So we have now successfully created a tree data structure in swift very very simply and we have seen
how it works.
I'm sure you can imagine how this is helpful for organizing data in a very structured way.
And yeah very cool stuff guys.
This is Caleb with slopes dot com and I'll see in the next video.