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:
- a data value
- a pointer to its left child
- a pointer to its right child
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
-
Draw a binary tree whose root has only a left child. Identify every empty subtree.
-
For the tree shown below, state the data stored at the root and the left and right children of the root.
M / \ P Q -
Write a
Nodestructure for a binary tree that stores integer data and has left and right child pointers.
Common Mistakes
- Assuming that every node must have two children. A node may have zero or one subtree.
- Treating a missing left or right child as a separate data node. It is an empty subtree, commonly represented by
nullptr. - Confusing the root pointer with the data stored in the root. The pointer identifies the topmost node; the node stores the data.
Key Takeaways
- A binary tree is empty or consists of a node with at most two subtrees.
- A node can have zero, one, or two subtrees, and either subtree may be empty.
- A pointer-based node stores data plus left and right pointers.
- A root pointer identifies the tree, and
nullptrcan represent an empty tree or a missing child.
Sources
- https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/btree.htm — archive.nptel.ac.in. Accessed 24 September 2026.
- https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/traversal.htm — archive.nptel.ac.in. Accessed 24 September 2026.
- https://archive.nptel.ac.in/content/storage2/courses/111106050/Module3.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
- https://archive.nptel.ac.in/content/storage2/courses/downloads_new/106106130/PrgDSAssignmentQuestions.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
- https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_4.htm — archive.nptel.ac.in. Accessed 24 September 2026.
Sources
- Data Structures and Algorithms — NPTEL (Used as a reference for data structure terminology.)
- https://archive.nptel.ac.in/content/storage2/courses/111106050/Module3.pdf — archive.nptel.ac.in (Generated candidate citation)
- https://archive.nptel.ac.in/content/storage2/courses/downloads_new/106106130/PrgDSAssignmentQuestions.pdf — archive.nptel.ac.in (Generated candidate citation)
- https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/btree.htm — archive.nptel.ac.in (Generated candidate citation)
- https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/traversal.htm — archive.nptel.ac.in (Generated candidate citation)
- https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_4.htm — archive.nptel.ac.in (Generated candidate citation)