Binary Tree Data Structure from Scratch (2026)
A Binary Tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is the foundation for many advanced tree structures like Binary Search Trees, Heaps, and AVL Trees. Binary Trees are used in expression parsing, Huffman coding, and hierarchical data representation.
There are several types of binary trees including Full (every node has 0 or 2 children), Complete (all levels filled except possibly last), Perfect (all internal nodes have 2 children and all leaves are at the same level), and Skewed (nodes have only one child). Understanding these categories is essential for selecting the right tree for a given problem.
Tree Traversals
Traversal is visiting every node exactly once. Inorder (Left-Root-Right) visits nodes in sorted order for BSTs. Preorder (Root-Left-Right) creates a copy of the tree. Postorder (Left-Right-Root) deletes the tree. Level-order uses a queue for breadth-first traversal.
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
void levelOrder(Node* root) {
queue q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front(); q.pop();
cout << cur->data << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
} Height and Size of Binary Tree
The height of a binary tree is the longest path from the root to a leaf. The size is the total number of nodes. Both can be computed recursively in O(n) time. The diameter (longest path between any two nodes) is another useful metric.
int height(Node* root) {
if (!root) return 0;
return 1 + max(height(root->left), height(root->right));
}
int size(Node* root) {
if (!root) return 0;
return 1 + size(root->left) + size(root->right);
}Frequently Asked Questions
What is the difference between Complete and Perfect Binary Tree?
A Complete Binary Tree has all levels filled except possibly the last, which fills left to right. A Perfect Binary Tree has all internal nodes with 2 children and all leaves at the same level.
How is a Binary Tree stored in memory?
Each node stores data and pointers to left and right children. For array-based storage (used in heaps), the root is at index 0, left child at 2i+1, and right child at 2i+2.
Originally published on Ayodhyyya. Last updated June 1, 2026.