Introduction to Binary Trees

What is a Binary Tree?

A binary tree is a type of data structure in which each node has at most two children, referred to as the left child and right child. A binary tree has a hierarchical structure that consists of a set of connected nodes, with one node designated as the root. Binary trees are widely used in computing because of their efficient organization and manipulation of data.

Binary trees form the foundation for many other tree-based data structures like binary search trees (BST), AVL trees, heaps, and expression trees.

Structure of a Binary Tree

A binary tree is made up of nodes. Each node in the tree contains:

  • Data/Value: The value or data stored in the node.
  • Left Child: A pointer/reference to the left child (or null if there is no left child).
  • Right Child: A pointer/reference to the right child (or null if there is no right child).

Representation of a Binary Tree:

Here is a binary tree structure:

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

In this tree:

  • A is the root node.
  • B and C are children of A.
  • D and E are children of B, while F is the right child of C.
  • D, E, and F are leaf nodes as they have no children.

Types of Binary Trees

  1. Full Binary Tree:

    • Every node in the tree has either 0 or 2 children.

    • Example:

      plaintext
          A
   / \
  B   C
 / \
D   E
  2. Complete Binary Tree:

    • All levels are completely filled except possibly the last level, and all nodes are as left as possible.

    • Example:

      plaintext
          A
   / \
  B   C
 / \
D   E
  3. Perfect Binary Tree:

    • A binary tree in which all internal nodes have exactly two children, and all leaf nodes are at the same level.

    • Example:

      plaintext
          A
   / \
  B   C
 / \ / \
D  E F  G
  4. Balanced Binary Tree:
    • A tree where the height of the left and right subtrees of every node differs by at most 1.
    • Balanced trees ensure that operations like insertion, deletion, and search can be performed efficiently in O(log n) time.
  5. Degenerate (Skewed) Binary Tree:

    • A binary tree in which each parent node has only one child, resembling a linked list.

    • Example (Left-skewed):

      plaintext
          A
   /
  B
 /
C

Binary Tree Traversals

Traversing a binary tree means visiting each node in a specific order. There are several types of binary tree traversals:

  1. Inorder Traversal (Left, Root, Right):

    • Visit the left subtree, the root node, and then the right subtree.

    • Example:

      plaintext
          A
   / \
  B   C
 / \
D   E

    • Inorder Traversal: D, B, E, A, C

    • Commonly used for binary search trees (BST) as it gives nodes in non-decreasing order.

  2. Preorder Traversal (Root, Left, Right):
    • Visit the root node first, then the left subtree, and finally the right subtree.
    • Preorder Traversal for the above tree: A, B, D, E, C
    • Useful for creating a copy of the tree.
  3. Postorder Traversal (Left, Right, Root):
    • Visit the left subtree, then the right subtree, and finally the root node.
    • Postorder Traversal for the same tree: D, E, B, C, A
    • Useful for deleting nodes or evaluating expressions in an expression tree.
  4. Level Order Traversal (Breadth-First Search):

    • Visit the nodes level by level, starting from the root.

    • Example:

      plaintext
          A
   / \
  B   C
 / \
D   E

    • Level Order Traversal: A, B, C, D, E

    • Useful for finding the shortest path in graph algorithms or tree structures.

Properties of Binary Trees

  1. Height of a Binary Tree:

    • The height of a tree is the number of edges from the root to the deepest leaf node.

    • For example, in the tree:

      plaintext
          A
   / \
  B   C
 /
D

    • The height is 2 (from A to D).

  2. Number of Nodes in a Full Binary Tree:
    • A full binary tree with height h has 2^h - 1 nodes.
  3. Number of Leaf Nodes:
    • In a perfect binary tree, the number of leaf nodes is 2^(h - 1) where h is the height of the tree.
  4. Relationship between Height and Number of Nodes:
    • The minimum height of a binary tree with n nodes is log₂(n), and the maximum height is n - 1 (for a skewed tree).

Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of binary tree where:

  • The left subtree of a node contains only nodes with values less than the node’s value.
  • The right subtree of a node contains only nodes with values greater than the node’s value.
  • Both left and right subtrees must also be binary search trees.

BSTs allow for efficient searching, insertion, and deletion operations in O(log n) time, provided the tree is balanced.

Example of a Binary Search Tree:

plaintext
        50
       /  \
      30   70
     /  \  / \
    20  40 60 80

In a BST, inorder traversal always gives a sorted sequence of values.

Here are examples of creating and traversing a binary tree in C++, Java, and Python.

C++ Implementation of a Binary Tree

cpp
#include <iostream>
using namespace std;

// Definition of a tree node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Inorder Traversal (Left, Root, Right)
void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    // Construct the binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    // Perform inorder traversal
    cout << "Inorder Traversal: ";
    inorderTraversal(root);

    return 0;
}

Java Implementation of a Binary Tree

java
// Definition of a tree node
class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

public class Main {
    // Inorder Traversal (Left, Root, Right)
    public static void inorderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.data + " ");
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        // Construct the binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        // Perform inorder traversal
        System.out.print("Inorder Traversal: ");
        inorderTraversal(root);
    }
}

Python Implementation of a Binary Tree

python
# Definition of a tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Inorder Traversal (Left, Root, Right)
def inorder_traversal(root):
    if root is None:
        return
    inorder_traversal(root.left)
    print(root.data, end=" ")
    inorder_traversal(root.right)

# Main function
if __name__ == "__main__":
    # Construct the binary tree
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    # Perform inorder traversal
    print("Inorder Traversal: ", end="")
    inorder_traversal(root)

Applications of Binary Trees

  1. Binary Search Trees (BSTs):
    • Used to store sorted data and perform fast searches, insertions, and deletions.
  2. Heaps:
    • Binary trees are used to implement heaps (e.g., max-heap, min-heap), which are used in priority queues and sorting algorithms like Heap Sort.
  3. Expression Trees:
    • Binary trees are used to represent arithmetic expressions, where internal nodes are operators and leaf nodes are operands. These trees are useful in parsing expressions and generating code.
  4. File Systems:
    • Binary trees are used to organize hierarchical structures like file systems, where directories contain subdirectories and files.
  5. Networking:
    • Binary trees are used in network routing algorithms to efficiently manage the routes between different devices or systems.

DSA

6499

168

Related Articles