Non-Linear Data Structure
Introduction to Trees
This lesson introduces tree data structures. We'll explore their
usefulness and basic terminology. Learn about nodes, roots,
edges, and more. Discover real-world examples like file
systems and organizational charts.
by Jade Lebrias
Trees
Tree in the computer field is also referred to as
the real-world tree however the difference
between the
real world and the computing field tree is that it
is visualized as upside down and root on top of it
and branch
from root to tree leaves.
Tree Terminology:
Anatomy of a Tree
Node
A fundamental unit containing data. These are the ones
being connected by edges
or lines.
Root
The topmost node, the entry point. this node will have no
parents at all. Any nodes can be a root node as long as it is
rooted as a parent node.
Edges
The connecting link between any two nodes. In a
tree with 'N' number of nodes there will
be a maximum of 'N-1' number of edges.
Child node
If the node is a descendant of any node, then
the node is known as a child node.
• B and C are children of A
• D, E and F are children of B
• I and J are children of E
• G and H are children of C
• K is child of G
Parent Node
The node which is a predecessor of any node. In
simple words, the node which has
a branch from it to any other node is called a
parent node. Parent node can also be defined as
"The
node which has child / children".
Internal Nodes
Any node of a tree that has child nodes.
Leaf Nodes
A node that has no children. Note that there can
only be one root node but there can
be many leaves. Leaves, also known as terminal
nodes, have a zero degree. There can be only
one root in a tree, but there can be many leaves.
Sibling
The nodes that have the same parent are known
as siblings.
• B and C are siblings
• D, E and F are siblings
• G and H are siblings
• I and J are siblings
Subtree
A subtree is viewed as a complete tree itself
which consist of children and its children’s
children and so on. The subtree corresponding to
the root node is called the entire tree; the
subtree
corresponding to any other node is called a
proper subtree.
Degree
The total number of children of a node of that
Node. In simple words, the Degree of a node
is total number of children it has. The highest
degree of a node among all the nodes in a tree is
called as 'Degree of Tree'.
• Degree of A is 2
• Degree of B is 3 (Degree of Tree)
• Degree of C is 2
• Degree of E is 2
• Degree of G is 1
Levels
The levels are generations that a tree has starting on the root.
The root node is said to
be at Level 0 and the children of root node are at Level 1 and
the children of the nodes which are
at Level 1 will be at Level 2 and so on... In simple words, in a
tree each step from top to bottom is
called as a Level and the Level count starts with '0' and
incremented by one at each level.
Depth of the tree
The total number of edges from root node to a particular node
is called
as DEPTH of that Node. In a tree, the total number of edges
from root node to a leaf node in the
longest path is said to be Depth of the tree. In simple words,
the highest depth of any leaf node in
a tree is said to be depth of that tree. In a tree, depth of the
root node is '0'.
Height
In a tree data structure, the total number of
edges from leaf node to a particular node in the
longest path is called as HEIGHT of that Node. In
a tree, height of the root node is said to be height
of the tree. In a tree, height of all leaf nodes is
'0'.
Traversing
The sequence of Nodes and Edges from one node
to another node is called
as PATH between that two Nodes.
Types of Trees: Binary Trees
Definition Use Cases
Each node has at most two children: left and right. Binary search trees, expression trees, Huffman coding trees
Types of Trees: Binary Search Trees (BSTs)
Search Insertion Deletion Min/Max
Find a node efficiently. Add a new node. Remove a node. Find smallest/largest value.
Types of Trees: Balanced
Trees
1 Problem
Unbalanced BSTs lead to O(n) performance.
2 Solution
Balanced trees adjust to maintain balance.
3 Examples
AVL Trees, Red-Black Trees.
4 Benefits
Guaranteed O(log n) performance.
Tree Traversal Algorithms
Preorder Inorder Postorder Level-Order
(Root, Left, Right). (Left, Root, Right). (Left, Right, Root). Visit level by level.
Useful for prefix Sorted order in BSTs. Deleting a tree.
expressions.
Applications of Trees: Beyond the Basics
Compilers 1
Parse code into ASTs.
2 Databases
Indexing data (B-trees).
Networking 3
Routing algorithms.
4 Machine Learning
Decision trees.
File Systems 5
Directory structure.
Summary and Next Steps
Key Takeaways
Trees are hierarchical structures. Balanced trees are important.
Further Learning
Implement tree operations. Explore advanced structures.
