EdTech

3 · Trees · Data Structures

Binary Trees

·

What Is a Binary Tree?

A binary tree is either empty or consists of a node with at most two subtrees. Each subtree is itself a binary tree, so the definition is recursive.

Nodes, Children, and Empty Subtrees

A node can have zero, one, or two subtrees. Either subtree may be empty.

      A
     / \
    B   C

In this tree, A is the topmost node. B is its left child, and C is its right child. Because B and C have no children shown, each has empty left and right subtrees.

A node does not need to have both children:

    A
     \
      C

Here, A has an empty left subtree and a right subtree containing C.

Representing a Binary Tree with Pointers

In a pointer-based representation, each node stores:

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

A pointer to the root identifies the whole tree. If the tree is empty, the root pointer can be nullptr.

Node* root = nullptr;

The following creates a tree with A as the root and B and C as its children:

Node* root = new Node{'A', nullptr, nullptr};
root->left = new Node{'B', nullptr, nullptr};
root->right = new Node{'C', nullptr, nullptr};

The nullptr values show that a child pointer does not lead to another node. For example, root->left points to B, while B’s left and right pointers are nullptr.

Practice

  1. Draw a binary tree whose root has only a left child. Identify every empty subtree.

  2. For the tree shown below, state the data stored at the root and the left and right children of the root.

        M
       / \
      P   Q
  3. Write a Node structure for a binary tree that stores integer data and has left and right child pointers.

Common Mistakes

Key Takeaways

Sources

  1. https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/btree.htm — archive.nptel.ac.in. Accessed 24 September 2026.
  2. https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/traversal.htm — archive.nptel.ac.in. Accessed 24 September 2026.
  3. https://archive.nptel.ac.in/content/storage2/courses/111106050/Module3.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
  4. https://archive.nptel.ac.in/content/storage2/courses/downloads_new/106106130/PrgDSAssignmentQuestions.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
  5. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_4.htm — archive.nptel.ac.in. Accessed 24 September 2026.

Sources

  1. Data Structures and Algorithms — NPTEL (Used as a reference for data structure terminology.)
  2. https://archive.nptel.ac.in/content/storage2/courses/111106050/Module3.pdf — archive.nptel.ac.in (Generated candidate citation)
  3. https://archive.nptel.ac.in/content/storage2/courses/downloads_new/106106130/PrgDSAssignmentQuestions.pdf — archive.nptel.ac.in (Generated candidate citation)
  4. https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/btree.htm — archive.nptel.ac.in (Generated candidate citation)
  5. https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/traversal.htm — archive.nptel.ac.in (Generated candidate citation)
  6. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_4.htm — archive.nptel.ac.in (Generated candidate citation)

Related topics