1.2) Binary Tree

What is a Binary Tree?

A Binary Tree is a type of data structure where each node can have at most two children.

It’s like a branching structure where each node has the potential to lead to two other nodes.

This structure is used in various computer science applications to organize and manage data.

Let’s use a simple example to illustrate a Binary Tree:

        5
      /   \
     3     8
    / \
   2   4

In this example:

• The number in each node represents its value or data.
• The top node, labeled ‘5’, is the root of the tree. It has two children: ‘3’ on the left and ‘8’ on the right.
• The ‘3’ node has two children: ‘2’ on the left and ‘4’ on the right.
• The ‘8’ node has no children.

Binary Tree Key Terminology:

• Node: Each circle in the tree represents a node. It holds some data and can have up to two children.
• Root: The topmost node of the tree, from which everything else branches out.
• Child: A node directly connected to another node when moving away from the root.
• Parent: The opposite of a child. A node is a parent to its children.
• Leaf: A node with no children. It’s like the end of a branch.
• Edge: The line connecting a parent node to its child nodes.

Why Binary Trees?

Binary Trees have many applications in computer science, such as:

1. Searching and Sorting: Binary Search Trees (a type of Binary Tree) make searching and sorting data efficient.
2. Hierarchical Data: They’re used for representing hierarchies like organization charts or file systems.
3. Expression Evaluation: Binary Trees can be used to evaluate mathematical expressions.
4. Data Compression: In Huffman coding, Binary Trees are used to compress data.
5. Game Development: They’re used in decision trees for making choices in games.

Binary Tree Traversal:

Traversing a Binary Tree means visiting each node in a specific order. There are three common ways to traverse a Binary Tree:

1. In-Order: Left-Root-Right. Traverse the left subtree, visit the root, then traverse the right subtree.
2. Pre-Order: Root-Left-Right. Visit the root, traverse the left subtree, then traverse the right subtree.
3. Post-Order: Left-Right-Root. Traverse the left subtree, traverse the right subtree, then visit the root.

Here’s how these traversals look on our example tree:

• In-Order: 2, 3, 4, 5, 8
• Pre-Order: 5, 3, 2, 4, 8
• Post-Order: 2, 4, 3, 8, 5

Understanding Binary Trees and their traversals is fundamental for many aspects of computer science and programming. They help us efficiently manage and work with data in a structured manner.

Properties of Binary Trees:

1. Height (Depth): The length of the longest path from the root to a leaf. In the above tree, the height is 3.
2. Balanced Tree: A Binary Tree is balanced if the height of the left and right subtrees of every node differs by at most one.
3. Full Binary Tree: A Binary Tree is full if every node has either 0 or 2 children. No node has only one child.
4. Complete Binary Tree: A Binary Tree is complete if all levels are completely filled except possibly the last level, which is filled from left to right.