Binary Tree
🌱 What Is a Tree?
Before we get to binary trees, let’s first understand what a tree is in general.
In the real world, a tree grows from a single trunk that branches out into smaller parts — and those branches split again into even smaller ones.
In computer science, a tree structure works in almost the same way — except that it grows upside down! 😄
At the top, we have a single root node, and from it, smaller child nodes branch out.
Each connection between nodes is called an edge.
🌳 What Is a Binary Tree?
A binary tree is a special kind of tree where each node can have at most two children —
usually called the left child and the right child.
Here’s what it looks like:
[A]
/ \
[B] [C]
/ \ / \
[D] [E] [F] [G]In this example:
- A is the root (the topmost node).
- B and C are children of A.
- D and E are children of B, and so on.
Every arrow shows a parent–child relationship.
🧩 Structure of a Node
Each node in a binary tree typically contains three parts:
+---------+---------+---------+
| Left | Data | Right |
+---------+---------+---------+- Left → points to the left child.
- Data → holds the value (like a number or character).
- Right → points to the right child.
If a node doesn’t have a left or right child, that pointer is NULL (meaning it points to nothing).
🌿 Important Terms to Remember
Let’s go over some simple but useful words related to trees:
- Root: The very first (topmost) node of the tree.
- Parent: A node that has child nodes.
- Child: A node that comes from a parent node.
- Leaf: A node that has no children.
- Siblings: Nodes that share the same parent.
- Edge: The link connecting one node to another.
- Height of Tree: The number of edges in the longest path from the root to a leaf.
Example:
In the tree above,
- Root = A
- Leaves = D, E, F, G
- Height = 2 (A→B→D is one of the longest paths)
🌲 Types of Binary Trees
Binary trees come in a few common varieties, depending on how the nodes are arranged.
🔹 1. Full Binary Tree
Every node has either 0 or 2 children.
No node has only one child.
Example:
[A]
/ \
[B] [C]
/ \ / \
[D] [E] [F] [G]🔹 2. Complete Binary Tree
All levels are completely filled except possibly the last,
and all nodes in the last level are as far left as possible.
Example:
[A]
/ \
[B] [C]
/ \ /
[D] [E] [F]🔹 3. Perfect Binary Tree
Every internal node has exactly 2 children, and all leaves are at the same level.
Example:
[A]
/ \
[B] [C]
/ \ / \
[D] [E] [F] [G]🔹 4. Skewed Binary Tree
All nodes are arranged in a single line, like a linked list.
It can be:
- Left-skewed: all nodes have only a left child.
- Right-skewed: all nodes have only a right child.
Example (Right-skewed):
[A]
\
[B]
\
[C]
\
[D]🧠 Why Use Binary Trees?
You might wonder — why not just use arrays or linked lists?
Here’s why:
- Binary trees make searching and sorting faster.
- They provide hierarchical storage, which suits many real-world problems (like file systems).
- They’re the base for advanced structures like Binary Search Trees (BSTs), Heaps, and AVL Trees.
Think of them as the backbone of efficient data handling in computer science!
💡 Everyday Analogy
Imagine a family tree:
- At the top is the grandparent (root).
- They have children (parents).
- Those children have their own children (grandchildren).
Each person can have up to two children, just like in a binary tree.
It’s a perfect way to visualize how relationships and data connect in a structured way.
🪴 Example in Real Life
Let’s say you’re designing a decision-making system — like a quiz game.
A binary tree can represent yes/no questions:
[Is it an animal?]
/ \
Yes No
/ \
[Does it bark?] [Is it a plant?]
/ \ / \
Yes No Yes No
[Dog] [Cat] [Tree] [Rock]Each question leads to two possible paths, just like branches in a binary tree!
🧾 Summary Table
| Term | Meaning |
|---|---|
| Root | The topmost node |
| Parent | Node having child nodes |
| Child | Node derived from a parent |
| Leaf | Node without children |
| Height | Longest path from root to leaf |
| Edge | Connection between nodes |
🧩 Diagram (Simple Binary Tree)
[1]
/ \
[2] [3]
/ \ /
[4] [5] [6]Here:
- Root = 1
- Children of 1 → 2, 3
- Leaves → 4, 5, 6
- Height = 2
About the Author
