Trees: Basic To Advanced

Trees: Basic To Advanced

Ramandeep Singh's photo
Ramandeep Singh
·

2 min read

Table of contents

Hello everyone, I hope you are doing well, I am starting this blog for trees where I shall be teaching trees from the very basics to advance, Stay with me and I will make you get everything covered for your interviews as well as for CP :)

What are Trees?

While thinking about trees, the first thing that comes to our mind is the actual tree having roots, leaves, and so on but in programming, the terms are the same for the tree data structure but things change a little.

The tree in programming is inverted

yeah, it is very similar to this, the root is at the top and the leaves are at the bottom :)

Let's define the tree in data structures

Unlike other data structures, the tree is a hierarchical data structure where we have a root node which is at the top of the hierarchy, and leaf nodes at the bottom of the hierarchy.

The structure is very similar to the college system we have a director at the top level, then we have a principal/dean, followed by HODs, teachers, and finally students.

In the above image, I have shown how the college system resembles the tree rooted at node number 0, here, node 0 represents the director, and other nodes are called child nodes.

Let's define some terms related to trees:

A tree is a special type of graph having N nodes and N-1 edges.

There is exactly one path between any pair of nodes in the tree.

  1. Degree: It represents the number of edges connecting any node in the tree for example the root node 0 in the above tree has a degree of 1.

  2. Root: The node at the top of the tree with degree 1 is called the root node.

  3. Leaf: The node at the bottom of the tree is called the leaf node.

  4. Parent: The very first node in the path from any node n to the root node is the parent of the node n.

  5. Ancestor: All of the nodes that are parent nodes of a node and parent of parent are ancestors.

  6. Subtree: A subtree of a node n is the set of nodes that have n as an ancestor.

  7. Depth: The distance of a node from the root is called depth.

That's all I have got for today, Do like it and follow for further updates :D

TreeDSAalgorithmsnode