Binary Tree

A Binary Tree is one of the most important non-linear data structures in computer science. It is called a “binary” tree because each node in the tree can have a maximum of two children only.

These two children are specifically known as:

• Left Child
• Right Child

Unlike linear data structures such as arrays and linked lists where elements are arranged sequentially, binary trees organize data hierarchically.

Binary trees are widely used in:

• Searching algorithms
• Expression evaluation
• Database indexing
• Operating systems
• Artificial intelligence
• Decision-making systems
• Compiler design

Many advanced data structures are built using binary trees, such as:

• Binary Search Tree (BST)
• AVL Tree
• Heap
• Expression Tree
• Huffman Tree

Formal Definition of Binary Tree

A Binary Tree is defined as:

A finite collection of nodes which is either:

1. Empty, OR
2. Consists of:
   • A root node
   • A left subtree
   • A right subtree

Both left and right subtrees are themselves binary trees.

This recursive definition is very important because every smaller subtree inside a binary tree also behaves like a binary tree.

Structure of a Binary Tree

Each node in a binary tree contains three parts:

1. Data field
2. Pointer/reference to left child
3. Pointer/reference to right child

Example:

          A
         / \
        B   C
       / \   \
      D   E   F

Explanation:

• A is the root node.
• B is the left child of A.
• C is the right child of A.
• D and E are children of B.
• F is the right child of C.

Important Characteristics of Binary Tree

1. Maximum Two Children

Each node can have:

• Zero child
• One child
• Two children

But no node can have more than two children.

2. Ordered Structure

The left child and right child are treated differently.

Example:

      A
     / \
    B   C

is different from:

      A
     / \
    C   B

because positions matter.

3. Recursive Nature

Every subtree of a binary tree is also a binary tree.

Example:

        A
       / \
      B   C
     / \
    D   E

The subtree rooted at B is itself another binary tree.

4. Hierarchical Structure

Binary trees represent parent-child relationships naturally.

Binary Tree Terminology

Understanding terminology is very important for solving numerical and theoretical questions.

1. Root Node

The topmost node of the binary tree is called the root node.

Example:

        A
       / \
      B   C

Here: A = Root Node

Properties:

• A binary tree can have only one root.
• The root has no parent.

2. Parent Node

A node that has child nodes is called a parent node.

Example:

        A
       / \
      B   C

Here:

• A is the parent of B and C.

3. Child Node

A node directly connected below another node is called a child node.

Example:

• B and C are children of A.

4. Sibling Nodes

Nodes having the same parent are called sibling nodes.

Example:

        A
       / \
      B   C

B and C are siblings because they share the same parent.

5. Leaf Node

A node having no children is called a leaf node.

Example:

          A
         / \
        B   C
       / \
      D   E

Leaf nodes are: D, E, C

Leaf nodes are also called terminal nodes.

6. Internal Node

A node having at least one child is called an internal node.

Example: A and B

7. Edge

The connection between two nodes is called an edge.

Example: A → B

A binary tree with n nodes always contains: n - 1 edges

Reason:

• Root node does not need any edge.
• Every additional node requires one edge to connect to the tree.

8. Degree of a Node

The number of children of a node is called its degree.

Example:

        A
       / \
      B   C

• Degree of A = 2
• Degree of B = 0
• Degree of C = 0

Maximum degree in a binary tree is always 2.

9. Depth of a Node

Depth is the distance from the root node to a particular node.

Example:

        A
       / \
      B   C
     /
    D

Depths:

• Depth of A = 0
• Depth of B = 1
• Depth of D = 2

10. Level of a Node

Level indicates the layer number of a node.

Example:

11. Height of Tree

Height is the number of edges in the longest path from root to leaf node.

Example:

        A
       / \
      B   C
     /
    D

Longest path: A → B → D

Height = 2

12. Subtree

A smaller tree formed from a node and its descendants is called a subtree.

Example:

        B
       / \
      D   E

is a subtree.

Types of Binary Trees

Different binary trees are designed for different purposes.

1. Strictly Binary Tree

A binary tree where every node has either:

• 0 children
  OR
• 2 children

No node can have only one child.

Example:

        A
       / \
      B   C
     / \
    D   E

Valid Strictly Binary Tree.

Invalid Example:

      A
     /
    B

because node A has only one child.

2. Full Binary Tree

A Full Binary Tree is often used interchangeably with Strictly Binary Tree.

Properties:

• Every node has either 0 or 2 children.

Example:

          A
         / \
        B   C
       / \ / \
      D  E F  G

3. Perfect Binary Tree

A Perfect Binary Tree is a full binary tree where:

• All internal nodes have exactly two children.
• All leaf nodes are at the same level.

Example:

          A
         / \
        B   C
       / \ / \
      D  E F  G

Properties:

• Total nodes = 2^(h+1) - 1
• Leaf nodes = 2^h

where h is the height.

4. Complete Binary Tree

A Complete Binary Tree is a binary tree where:

• All levels are fully filled except possibly the last level.
• Last level nodes are filled from left to right.

Example:

          A
         / \
        B   C
       / \  /
      D  E F

This is complete because nodes are filled left to right.

5. Degenerate or Skewed Binary Tree

A tree where each parent has only one child.

Example:

A
 \
  B
   \
    C

This structure behaves similarly to a linked list.

Types:

• Left Skewed Tree
• Right Skewed Tree

Binary Tree Operations

Several important operations are performed on binary trees.

1. Insertion Operation

Insertion means adding a new node into the binary tree.

In a general binary tree, insertion usually follows: Level-order insertion

This means:

• Fill nodes level by level
• From left to right

Example:

Initial tree:

      1
     / \
    2   3

Insert 4

Step-by-step:

• Left child of 2 is empty.
• Insert 4 there.

Result:

      1
     / \
    2   3
   /
  4

2. Traversal Operation

Traversal means visiting all nodes of the tree.

There are four major traversal methods.

A. Inorder Traversal

Order: Left → Root → Right

Example:

        A
       / \
      B   C
     / \
    D   E

Traversal: D → B → E → A → C

Important:

• In BST, inorder traversal gives sorted order.

B. Preorder Traversal

Order: Root → Left → Right

Traversal: A → B → D → E → C

Used for:

• Copying trees
• Expression trees

C. Postorder Traversal

Order: Left → Right → Root

Traversal: D → E → B → C → A

Used in:

• Deletion operations
• Expression evaluation

D. Level-order Traversal

Traversal level by level using queue.

Example: A → B → C → D → E

3. Search Operation

Searching means finding whether a value exists inside the tree.

Approaches:

• DFS Traversal
• BFS Traversal

In ordinary binary trees:

• Entire tree may need traversal.

In BST:

• Searching becomes faster.

4. Deletion Operation

Deletion removes a node from the tree.

Case 1: Deleting Leaf Node

Simply remove the node.

Example:

    A
   /
  B

Delete B.

Case 2: Node with One Child

Replace node with its child.

Case 3: Node with Two Children

Replace with:

• Inorder successor or
• Inorder predecessor

Example:

     50
    /  \
  30    70

Delete 50.

Replace with 70.

5. Height Calculation

Height = longest path from root to leaf.

Example: A → B → D

Height = 2

6. Counting Nodes

• Total Nodes: Count all nodes recursively.
• Leaf Nodes: Nodes without children.
• Internal Nodes: Nodes having at least one child.

7. Mirror Operation

Swap left and right subtrees.

Example:

Before:

      1
     / \
    2   3

After mirror:

      1
     / \
    3   2

8. Balanced Tree Checking

A binary tree is balanced if:

Height difference between left and right subtree ≤ 1

Balanced trees improve performance.

9. Finding Maximum and Minimum

In normal binary tree:

• Entire tree traversal required.

In BST:

• Leftmost node = minimum
• Rightmost node = maximum

10. Diameter of Tree

Diameter is the length of the longest path between any two nodes.

Example:

D → B → A → C

Rules for Creating General Binary Tree

When creating a general binary tree:

• Each node can have 0, 1, or 2 children.
• No sorting rule exists.
• Insertion usually follows level-order strategy.

Level-order Construction Example

Given data:

12, 18, 14, 15, 13, 7, 9, 11, 8, 3

Construction steps:

1. 12 becomes root.
2. 18 becomes left child of 12.
3. 14 becomes right child of 12.
4. 15 becomes left child of 18.
5. 13 becomes right child of 18.
6. 7 becomes left child of 14.
7. 9 becomes right child of 14.
8. 11 becomes left child of 15.
9. 8 becomes right child of 15.
10. 3 becomes left child of 13.

Final tree:

              12
           /      \
         18        14
       /   \      /   \
     15    13    7     9
    /  \   /
  11   8  3

Binary Tree Representation

Binary trees are represented in memory using two methods.

1. Array Representation

Nodes are stored level by level inside arrays.

Rules:

• Parent at index i
• Left child = 2i + 1
• Right child = 2i + 2

Example:

      1
     / \
    2   3

Array:

Index: 0 1 2
Value: 1 2 3

Advantages:

• Fast indexing
• Good for complete trees

Disadvantages:

• Memory waste in sparse trees

2. Linked Representation

Each node contains:

• Data
• Left pointer
• Right pointer

Structure:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

Advantages:

• Flexible
• Efficient for sparse trees

Disadvantages:

• Extra pointer memory required

Applications of Binary Tree

Binary trees are used in:

• Binary Search Trees
• Heaps
• Expression Trees
• Decision Trees
• Syntax Trees
• Huffman Coding
• Artificial Intelligence
• Database systems

Advantages of Binary Tree

1. Efficient searching
2. Hierarchical representation
3. Dynamic memory allocation
4. Efficient traversal techniques
5. Foundation for advanced structures

Disadvantages of Binary Tree

1. Complex implementation
2. Extra memory for pointers
3. Unbalanced trees reduce efficiency
4. Recursive algorithms may increase overhead

Time Complexity

Worst case occurs in skewed trees.

Numerical Questions on General Binary Tree Creation

1. Create a general binary tree using the following level-order data: 25, 30, 15, 20, 10, 35, 40
   • Draw the tree.
   • Identify root, leaf, and internal nodes.
2. Given the data: 50, 20, 70, 10, 30, 60, 90, 5
   • Construct a general binary tree in level order.
   • Show the left and right child for each node.
3. Construct a general binary tree from the following data sequence: 8, 12, 6, 10, 5, 7
   • Draw the tree.
   • Write the preorder, inorder, and postorder traversals.
4. Insert the following values into a general binary tree using level-order strategy: 1, 2, 3, 4, 5, 6, 7, 8
   • Draw the resulting binary tree.
   • Count the number of:
   • Leaf nodes
   • Internal nodes
   • Total nodes
   • Height of the tree
5. Given numerical data: 100, 200, 300, 400, 500, 600
   • Build a general binary tree using level-order.
   • Represent the tree as an array (binary tree in array form).
6. Given the data values: 11, 22, 33, 44, 55, 66, 77, 88, 99
   • Construct the binary tree using level-order.
   • Perform inorder traversal and list the result.
7. Create a general binary tree from the data: 10, 5, 15, 2, 7, 12, 20, 1
   • Draw the tree.
   • What is the level of node 12?
   • What is the parent of node 1?

Conclusion

A Binary Tree is one of the most fundamental and powerful non-linear data structures in computer science. It organizes data hierarchically and allows efficient searching, insertion, deletion, and traversal operations.

Understanding binary trees is extremely important because many advanced data structures and algorithms are based on them. Mastering binary trees builds a strong foundation for topics like Binary Search Trees, AVL Trees, Heaps, Graphs, and Artificial Intelligence systems.