Interview Prep:  Binary and General Trees

Published: 2020-11-18 23:08:18

In your study of data structures, perhaps you’ve only gotten to the linear structures, e.g. stacks, queues, linked lists.  Think of these as one dimensional like a street-- you can only go up or down that street.  Now let’s consider a multi-dimensional data structure: trees.  A tree has one main trunk, but it can have branches.  And those branches can have their own branches, like this:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/mhk6x37xw2v73o2ancry.png)


So what does a tree look like as a data structure?

First, let’s remember from our linear data structures that those structures consisted of  nodes of data.  Each node pointed to the next node:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/hbw3lltk7q3ngt30chth.png)


In trees, the difference is that each node can point to more than one node:



In the above image, we have 4 nodes: A, B, C and D.

The A node is called the **root**, because all other nodes branch off from A.  We can even say, “A is the **parent** of B, C and D.   B, C, and D are the **children** of A

##Siblings 

 Let’s learn some more terminology with this tree below:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/4n18ekx3kyojjo0yq3vi.png)

Above, we see node A is the root and B, C , D are A’s children.  However, because B, C, D are on the same level (“Same level” means you can draw a horizontal line connecting the lengths of B, C, D) these nodes are also **siblings** of each other.

##Ancestors and Descendants

See the tree below:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/fl2zu1i956ynvgeq5n6z.png)


In the image above, we see three nodes: A, B and E circled in pink.  Just like in a family tree diagram,  E’s “parent” or **ancestor** is B.  But the “family line” extends further back to A.  A is also an ancestor of E.

We can also look at it in the opposite direction with the nodes circled in blue highlighting nodes D, G, H, and I.  D has two “children” or **descendants**: G and H.  However, D’s “family line” extends further through H to I.  I is also a descendant of D.

##Leaves

Here’s another tree:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/eamafuhsqicmg0lmjckk.png)

Sometimes nodes don’t have children.  In that case, these child-less nodes are called **leaves** (think of a leaf on a tree blowing around in the wind untethered by any branches beyond it).  A leaf can also be called **external** (Think of the leaf blowing in the wind as a conduit to the outside world; no further branches are blocking it.

If leafs can be termed external, what would we call those nodes who do have at least 1 child?  Yep, those nodes are **internal**.


###Path and Path Length

Given a tree where we select two different nodes of that tree, a **path** is the set of edges from one node to the other.  The **path length** is the number of edges in that path:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ewxmiixuxhu59seg6br6.png)

In the above diagram, we want to get from the root, A, to H.   You see the path was traced out for us in blue.  Each of those arrows that point from a parent node to a child node is called an **edge**.  We see it took 3 edges to get from A to H.  

###Node Level and Node Depth

Let’s describe a way to tell how deep down a given node is nested:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/tbhg8uvwzoqiky0oibh4.png)

In the image above, we define the root level to be “0”.  Each succeeding level increases by 1. The terms “level” and “depth” are used interchangeably.

For example, we see that Node C is at a depth (or level) of 1.  Node H is at a depth of 3.


Another related concept is the height of a tree:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/9ug6emkq7u02ebqh7iks.png)

In this example, we can determine the height of a tree by just counting levels--the trick is that we have to start with “0”.  So node A is at a height of 0; B, C, and D are at a height of 1.  E, F, and G are at a height of 2 and finally node H is at a height of 3.  Our tree’s height is then 3.


###Degree

Look at this example:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/i1itdpl7orddwfho3l9c.png)

First of all its height is 2.  Can you tell?

Then, we look at the maximum number of possible children for every node in the tree.  We see that the maximum number is 3. 

We can say that our tree has a height of 2 and a degree of 3.



##Types of Trees

The last thing we’ll look at today are types of trees.

You can have a tree where each node has any number of children from 0 to n.  The number of children each node has can be different from parent node to parent node.  In this case, we have a **general tree**

On the other hand, we can have a tree where every parent has at most ***n*** children.   The most popular version of this kind of tree is where n = 2.  In this case we have a **binary tree**.

 Here’s an example of a binary tree:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/bz2zfaipcefzer4crns9.png)

Notice how we have the root at node 1.  Then each child or descendant of node 1 has at either 0, 1 or 2 children.

So there you have most of the basic terminology to be able to work with trees.  Most of our work going forward will be with binary trees--as my tutor told me, binary trees represent about 95% of the work with trees.

More to come!

Keep coding out your dreams!

Namaste!