What Is Binary Tree With Example in Data Structure?

A binary tree is a fundamental data structure in computer science and is used to represent hierarchical relationships between elements. It consists of nodes, where each node can have at most two children – a left child and a right child. The topmost node is called the root, and the nodes at the bottommost level are known as leaf nodes.

Structure of a Binary Tree

A binary tree can be defined recursively. Each node in the tree contains three fields:

• Data: The value or information stored in the node.
• Left Child: A reference to the left child of the current node.
• Right Child: A reference to the right child of the current node.

Example of a Binary Tree

To better understand binary trees, let’s consider an example. Suppose we have a binary tree representing the family structure:

              John
             /    \
         Alice     Bob
        /     \      \
    Lisa   Mark   Sarah

In this example, John is the root of the tree. Alice and Bob are his children, where Alice is on the left and Bob is on the right. Similarly, Lisa and Mark are Alice’s children, while Sarah is Bob’s child.

Traversing a Binary Tree

To explore or visit all the nodes in a binary tree, we use various traversal algorithms. The three commonly used traversal techniques are:

1. In-order traversal: In this traversal, we visit (or process) nodes in ascending order when considering their values. For our example tree, an in-order traversal would yield: Lisa → Alice → Mark → John → Sarah → Bob.
2. Pre-order traversal: In this traversal, we visit the current node before its children.

   For our example tree, a pre-order traversal would yield: John → Alice → Lisa → Mark → Bob → Sarah.

3. Post-order traversal: In this traversal, we visit the current node after visiting its children. For our example tree, a post-order traversal would yield: Lisa → Mark → Alice → Sarah → Bob → John.

These traversals are essential for performing various operations on binary trees, such as searching for a specific node or printing the nodes in a particular order.

Conclusion

A binary tree is a versatile data structure that allows us to represent hierarchical relationships. It consists of nodes connected through left and right child references.

Traversing techniques like in-order, pre-order, and post-order help us explore the nodes efficiently. By understanding binary trees and their applications, you can enhance your problem-solving skills in computer science and software development.