Tree-based DSA I

• Tree Traversal
• Binary Tree

Tree Data Structure

• non-linear, hierarchical data structure consisting of nodes connected by edges

Why [use a] Tree Data Structure?

• different tree data structures allow quicker and easier access to data

---

Tree Terminologies

Node

• entity that contains key or value and pointers to child nodes
• last nodes of each path called leaf nodes or external nodes
  • do not contain link/pointer to child nodes
• any node having at least 1 child node called internal node

Edge

• link between any two nodes

Root

• topmost node of tree

Height of a Node

• number of edges from the node to the deepest leaf (i.e. the longest path from the node to a leaf node)

Depth of a Node

• number of edges from root to the node

Height of a Tree

• height of root node (or depth of deepest node)

Degree of a Node

• total number of branches of that node

Forest

• collection of disjoint trees

---

Types of Tree

• Binary Tree
• Binary Search Tree
• AVL Tree
• B-Tree

Tree Traversal

• tree traversal algorithm helps visit required node in tree
• see tree traversal

Tree Applications

• Binary Search Trees used to quickly check whether element is present in a set or not
• Heap is kind of tree used for heap sort
• modified version of tree called Tries used in modern routers to store routing information
• Most popular databases use B-Trees and T-Trees to store data
• Compilers use a syntax tree to validate syntax of every program you write