Introduction to Trees

The Trees are also somehow similar to Graph in terms of nodes and edges but it includes some extra constraints which defines its structure :

  • No cycles are present in a tree.
  • Only single path from node A to node B (A-->B) via edges.
  • There's always a path (or way) present from one node to another.

Using these constraints, we conclude, if there is a N nodes present then there must be N-1 edges for connecting these N nodes such that it forms a tree structure.

Let's discuss how can we approach the problems related to trees:

💡 Generally, you are given 'N' as integer which denotes number of nodes. Followed by 'N-1' subsequent lines which contain two space separated integers 'u' and 'v' whose values are from 1 ≤ {u, v} ≤ N which denotes that there is an edge between u & v.

After getting these inputs now you can proceed with storing its elements as we have done in the graph using a 2D dynamic array. One more thing to keep in mind that trees are all about the parent-child relationship that's why we need extra parent array where parent[i] tells the parent of the i-th node.

Now, how can we get the values inside the parent array 🤔 so for that we need to traverse all the nodes of the tree and the starting node will be termed as root of the tree.

Let's get more familiar with these concepts via c++ code :

Input output wala image aayega idhar

The above method tells you how you should store a tree for traversing and to perform any action. It will give you an idea that how you should proceed with any question related to the tree. Now, the logical operations that will perform on the tree to get the answer will be applied after this.

Practice some questions to get familiar with these topics.

This article is contributed by Rishabh Roshan

So that’s it for this article we will be coming up with our next article on further topics of Graph Theory very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding

By Programmers Army 😊