Release .8
What is a Tree in DSA?
In DSA, a tree is a data structure that looks like an upside-down tree.
It starts with a single node at the top, called the "root," and branches out into other nodes, which are connected by edges or lines. Each node can have zero or more "children" nodes, except for the root, which is the starting point.
Why Use Trees in DSA?
Trees are used in DSA because they are efficient for many types of data storage and retrieval tasks.
They help in organizing data in a structured way, making it easier to search, insert, and delete information.
Common Types of Trees:
- Binary Tree: Each node can have at most two children, typically referred to as the left child and the right child.
- Binary Search Tree (BST): A type of binary tree where the left child is smaller than the parent, and the right child is larger.
- AVL Tree: A type of balanced binary search tree where the heights of the left and right subtrees of any node differ by at most one.
- Heap: A specialized tree used in priority queue operations, with either a max-heap (parent node greater than children) or a min-heap (parent node smaller than children).
- Trie: A tree-like structure used for storing a dynamic set of strings or associative arrays where the keys are strings.
Terminologies used in trees:
Root: The topmost node of a tree is called the root. There is no edge pointing to it, but one or more than one edge originating from it. Here, A is the root node.
Parent: Any node which connects to the child. Node which has an edge pointing to some other node. Here, C is the parent of H.
Child: Any node which is connected to a parent node. Node which has an edge pointing to it from some other node. Here, H is the child of C.
Siblings: Nodes belonging to the same parent are called siblings of each other. Nodes B, C and D are siblings of each other, since they have the same parent node A.
Ancestors: Nodes accessible by following up the edges from a child node upwards are called the ancestors of that node. Ancestors are also the parents of the parents of that node. Here, nodes A, C and H are the ancestors of node I.
Descendants: Nodes accessible by following up the edges from a parent node downwards are called the descendants of that node. Descendants are also the child of the child of that node. Here, nodes H and I are the descendants of node C.
Leaf/ External Node: Nodes which have no edge originating from it, and have no child attached to it. These nodes cannot be a parent. Here, nodes E, F, G and I are leaf nodes.
Internal node: Nodes with at least one child. Here, nodes B, D and C are internal nodes.
Depth: Depth of a node is the number of edges from root to that node. Here, the depth of nodes A, C, H and I are 0, 1, 2 and 3 respectively.
Height: Height of a node is the number of edges from that node to the deepest leaf. Here, the height of node A is 3.
So that was it for the introductory part...
Covering the fundamentals of trees was just the tip of the iceberg.
Given the depth of this topic, I plan to break it into multiple segments, making it more easy for you to grasp without feeling overwhelmed.
I hope this post was informative and helpful.
If you have any questions, please feel free to leave a comment below.
Happy Coding 👍🏻!
Thank You
Top comments (0)