Binary Trees in Data Structure

Binary Trees in Data Structure 🌳

A Binary Tree is a hierarchical data structure in which each node has at most two children: a left child and a right child. It is widely used in searching, sorting, and hierarchical data representation.

---

📌 Key Properties of a Binary Tree:

✔ Each node has at most two children (left & right).
✔ The depth of nodes varies, affecting tree height.
✔ Can be balanced or unbalanced.

---

📌 Types of Binary Trees:

1️⃣ Full Binary Tree – Every node has 0 or 2 children (no single-child nodes).
2️⃣ Complete Binary Tree – All levels are completely filled, except possibly the last level, which is filled from left to right.
3️⃣ Perfect Binary Tree – All internal nodes have two children, and all leaf nodes are at the same level.
4️⃣ Balanced Binary Tree – The height difference between left and right subtrees is at most 1 (e.g., AVL Tree).
5️⃣ Degenerate (Skewed) Tree – Each parent node has only one child, making it look like a linked list.

---

📌 Binary Tree Traversal Methods:

🔹 Depth-First Traversal (DFS)

• Inorder (LNR) → Left → Root → Right
• Preorder (NLR) → Root → Left → Right
• Postorder (LRN) → Left → Right → Root

🔹 Breadth-First Traversal (BFS)

• Level Order Traversal → Visit nodes level by level

---

📌 Binary Search Tree (BST) – A Special Binary Tree

A Binary Search Tree (BST) is a binary tree that maintains a sorted order:
✅ Left subtree contains nodes less than the parent.
✅ Right subtree contains nodes greater than the parent.
✅ Enables efficient searching, insertion, and deletion in O(log n) time (if balanced).

---

📌 Applications of Binary Trees:

✅ Expression Trees – Used in compilers & mathematical expressions.
✅ Hierarchical Databases – Organizing data in databases.
✅ Decision Trees – Machine learning & AI-based models.
✅ Binary Heaps – Used in priority queues.
✅ Trie Structures – For fast word search in dictionaries.