Trees and their Basic Properties!
In this chapter, we are going to study the basics of the tree data structure!
We'll cover the following
Introduction
Trees consist of vertices (nodes) and edges that connect them. Unlike the linear data structures that we have studied so far, trees are hierarchical. They are similar to Graphs, except that a cycle cannot exist in a Tree - they are acyclic. In other words, there is always exactly one path between any two nodes.
- Root Node: A node with no parent nodes. Generally, trees don’t have to have a root. However, rooted trees have one distinguished node and are largely what we will use in this course.
- Child Node: A Node which is linked to an upper node (Parent Node)
- Parent Nodes: A Node that has links to one or more Child Nodes
- Sibling Node: Nodes that share same Parent Node
- Leaf Node: A node that doesn’t have any Child Node
- Ancestor Nodes: the nodes on the path from a node d to the root node. Ancestor nodes include node d’s parents, grandparents, and so on
The figure below shows all the terminologies described above:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.