DEV Community

Cover image for Everything you need to know about tree data structure
Anjan Shomooder
Anjan Shomooder

Posted on

Everything you need to know about tree data structure

In this blog, you will learn about tree data structure.

Before you learn about tree data structure let me tell you why this is useful. And a practical use of this data structure.

The practical example

If you are using a browser, that means you are using a tree data structure. If you don't believe open the developer tools of the browser using the F12 key. Go to inspect tab. If you are a front-end developer you know these.
Alt Text

The thing you are seeing is a tree. DOM(Document Object Model) is a tree. Even though it doesn't look like one. let's take a look at the tree representation of what you are seeing right now.

Alt Text

First, we have something called an HTML tag. Inside the HTML tag, there are two more tags called head and body. Inside head and body tags there are more tags. And again inside them, there are more tags. You can also notice that these tags are getting nested more and more. Each tag is connected to a previous tag without the first tag. And you might have noticed some hierarchy in here. This is what we call a tree data structure.

What is a tree data structure?

Alt Text
A tree data structure is a structure where each node is connected to a previous or parent node in a hierarchical order.

Ok. But that doesn't look like a tree. Let me prove it to you.

Alt Text
I hope this picture looks like a tree to you.

let's apply some CSS.

.tree {
    transform: rotate(180deg);
}
Enter fullscreen mode Exit fullscreen mode

Alt Text
We have just rotated our tree to 180 degrees. But it is still a tree. We have just rotated our tree to 180 degrees.

Let's see the properties and features of trees.

  • Node: You can think of a node as a leaf in a tree. A node is nothing but just an element of a tree.
    Alt Text

  • Root Node: A root node is a top node that you see in the tree. It does not have any previous node.
    Alt Text

  • Parent Node: The parent node is the immediate previous node connected to the current node. It is just like our real-life parents. A parent can have multiple children.
    Alt Text

  • Child Node: The child node is the children of the parent node. And that makes sense right. A child can also be a parent.
    Alt Text

  • Leaf Node: Less node is a child node but not a parent node. Or simply, a leaf node is a child node that no other node is connected to it from the bottom.
    Alt Text

  • Sibling Node: A sibling node is a child node connected to the same parent node. And that's what sibling means.
    Alt Text

  • Direction: The connection direction of a tree is always unidirectional or one way. It always goes from top to bottom. From root node to child node and its child node and so on. If you notice the picture you will get that.
    Alt Text

  • Edge: An edge in a tree is the connection between two nodes. Suppose the connection between you and your parent.
    Alt Text

  • Path: A path is nothing but consecutive edges between the source node to the given node.
    Alt Text

  • Ancestor Node: All the nodes that are in the path of a source node and the target node are called Ancestor nodes. Like your Father ----> GrandFather -----> Great GrandFather -----> so on

  • Descendant Node: Every node in the path of your current node to the leaf nodes is called an ancestor node.

Alt Text

  • Level: Count the number of edges in the path from the root node to your current node. That number of edges is called level.
    Alt Text

  • Depth of Node: From the root node to the given node path, count the number of edges. The total number of edges is the depth of that node.
    Alt Text

  • Height of Node: The total number of edges on the path from your current node to the most distant leaf node is the height of the node.
    Alt Text

  • Degree of a node: The total number of children of a node is the degree of a node.
    Alt Text

  • Height of Tree: Maximum number of edges from the root node to the leaf node. A tree might have many leaf nodes. But you have to look for the most distant node. Then count the edges.
    Alt Text

Some facts about Tree

  • The height of a tree is always equal to the level of the tree
  • Number of edges in the tree = (n - 1) [where n is the total number of the tree]

Common types of tree Data Structures.

  • General tree data
  • Binary tree
  • Binary Search Tree
  • AVL tree
  • Red-Black tree
  • Splay tree
  • Treap tree and ...so on

That's it for this blog.

Shameless Plug

I have made a video about how to build a carousel postcard with React, Material-UI, and Swiper.js.
If you are interested you can check the video.

You can also demo the application form here

Screenshot of Insta Carousel

Please like and subscribe to Cules Coding. It motivates me to create more content like this.

If you have any questions, please comment down below.
You can reach out to me on social media as @thatanjan .
Stay safe. Goodbye.

About me

Why do I do what I do?

The Internet has revolutionized our life. I want to make the internet more beautiful and useful.

What do I do?

I ended up being a full-stack software engineer.

What can I do?

I can develop complex full-stack web applications like social media applications or e-commerce sites.

What have I done?

I have developed a social media application called Confession. The goal of this application is to help people overcome their imposter syndrome by sharing our failure stories.
I also love to share my knowledge. So, I run a youtube channel called Cules Coding where I teach people full-stack web development, data structure algorithms, and many more. So, Subscribe to Cules Coding so that you don't miss the cool stuff.

Want to work with me?

I am looking for a team where I can show my ambition and passion and produce great value for them.
Contact me through my email or any social media as @thatanjan . I would be happy to have a touch with you.

Contacts

Email: thatanjan@gmail.com

linkedin: @thatanjan

portfolio: anjan

Github: @thatanjan

Instagram (personal): @thatanjan

Instagram (youtube channel): @thatanjan

twitter: @thatanjan

Blogs you might want to read:
Eslint, prettier setup with TypeScript and react
What is Client-Side Rendering?
What is Server Side Rendering?
Everything you need to know about tree data structure
13 reasons why you should use Nextjs

Videos might you might want to watch:





Discussion (0)