Binary Tree — Data Structures

Posted on by

🌱 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

TermMeaning
RootThe topmost node
ParentNode having child nodes
ChildNode derived from a parent
LeafNode without children
HeightLongest path from root to leaf
EdgeConnection 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