Binary Tree
A Binary Tree is a tree data structure in which every node has at most two children.
These two children are specifically called:
Left Child Right Child
The most important rule is:
A binary tree node can have 0, 1, or 2 children — never more than 2.
1. Basic Binary Tree
Example:
10 / \ 20 30 / \ \ 40 50 60
Here:
10→ Root20→ Left child of1030→ Right child of1040,50,60→ Leaf nodes
Notice that 30 has only one child.
That's completely valid.
30 \ 60
A binary tree does not require every node to have exactly two children.
2. Binary Tree Node
In C++, a binary tree node is usually represented as:
struct Node { int data; Node* left; Node* right; };
Each node contains:
Node / \ data pointers / \ left right
A complete constructor:
struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } };
3. Creating a Binary Tree Manually
Let's create:
10 / \ 20 30 / \ 40 50
C++:
#include <iostream> using namespace std; struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } }; int main() { Node* root = new Node(10); root->left = new Node(20); root->right = new Node(30); root->left->left = new Node(40); root->left->right = new Node(50); return 0; }
The connections are:
root ↓ 10 ├── left → 20 │ ├── left → 40 │ └── right → 50 │ └── right → 30
4. Important Binary Tree Terminology
Consider:
1 / \ 2 3 / \ / \ 4 5 6 7
Root
1
Internal nodes
1, 2, 3
Leaf nodes
4, 5, 6, 7
Height
There are 2 edges from root to the deepest leaves:
1 → 2 → 4
So:
height = 2
when height is measured in edges.
5. Types of Binary Trees
This is very important.
The major types are:
Binary Tree │ ├── Full Binary Tree ├── Complete Binary Tree ├── Perfect Binary Tree ├── Balanced Binary Tree └── Skewed Binary Tree
Let's understand each one.
6. Full Binary Tree
A Full Binary Tree is a binary tree where every node has either:
0 children OR 2 children
No node has exactly one child.
Example:
1 / \ 2 3 / \ / \ 4 5 6 7
Every node has either:
0 children → 4,5,6,7 2 children → 1,2,3
Therefore it is a Full Binary Tree.
Invalid example
1 / \ 2 3 \ 4
Node 3 has only one child.
Therefore it is not full.
7. Complete Binary Tree
A Complete Binary Tree has:
Every level completely filled except possibly the last level, and the last level is filled from left to right.
Example:
1 / \ 2 3 / \ / 4 5 6
The last level is:
4 5 6
filled from left to right.
So this is complete.
Not Complete
1 / \ 2 3 \ \ 5 7
There are gaps on the left before nodes appear on the right.
Therefore it is not complete.
8. Perfect Binary Tree
A Perfect Binary Tree has:
- Every internal node has exactly 2 children.
- Every leaf is at the same level.
Example:
1 / \ 2 3 / \ / \ 4 5 6 7
Everything is perfectly filled.
9. Perfect Binary Tree Formula
If height is h, the maximum number of nodes is:
2^(h+1) - 1
For height 2:
2^(2+1) - 1 = 2³ - 1 = 7
And our tree has:
7 nodes
10. Nodes at Each Level
For a binary tree:
Level 0 → maximum 1 node Level 1 → maximum 2 nodes Level 2 → maximum 4 nodes Level 3 → maximum 8 nodes
Generally:
Maximum nodes at level L = 2^L
Therefore the maximum number of nodes up to level h is:
1 + 2 + 4 + 8 + ... + 2^h
which equals:
2^(h+1) - 1
11. Balanced Binary Tree
A binary tree is generally considered height-balanced when the heights of the left and right subtrees of a node differ by at most a small amount, commonly 1.
Example:
10 / \ 5 20 / \ / \ 2 7 15 25
The tree is reasonably balanced.
A balanced tree keeps its height relatively small.
That's important because many tree operations depend on height.
12. Skewed Binary Tree
A skewed tree behaves almost like a linked list.
Left-skewed
5 / 4 / 3 / 2 / 1
Right-skewed
1 \ 2 \ 3 \ 4 \ 5
Its height becomes large.
For n nodes:
Balanced height ≈ O(log n) Skewed height = O(n)
This distinction becomes extremely important in Binary Search Trees.
13. Binary Tree Traversal
One of the most important parts of binary trees is traversal.
Traversal means:
Visit every node in a particular order.
The major traversals are:
1. Preorder 2. Inorder 3. Postorder 4. Level Order
The first three are usually DFS-style traversals.
14. Example Tree
We'll use this tree for the traversal examples:
1 / \ 2 3 / \ / \ 4 5 6 7
15. Preorder Traversal
Preorder means:
Root → Left → Right
Remember:
NLR
N = Node
L = Left
R = Right
For our tree:
1 / \ 2 3 / \ / \ 4 5 6 7
Visit:
1 ↓ 2 ↓ 4 ↓ 5 ↓ 3 ↓ 6 ↓ 7
Result:
1 2 4 5 3 6 7
16. Preorder C++ Code
void preorder(Node* root) { if (root == nullptr) { return; } cout << root->data << " "; preorder(root->left); preorder(root->right); }
Notice the order:
cout ↓ left ↓ right
That's:
N → L → R
17. Inorder Traversal
Inorder means:
Left → Root → Right
Remember:
LNR
For our tree:
1 / \ 2 3 / \ / \ 4 5 6 7
Traversal:
4 ↓ 2 ↓ 5 ↓ 1 ↓ 6 ↓ 3 ↓ 7
Result:
4 2 5 1 6 3 7
18. Inorder C++ Code
void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->data << " "; inorder(root->right); }
Order:
left ↓ root ↓ right
19. Postorder Traversal
Postorder means:
Left → Right → Root
Remember:
LRN
For our tree:
1 / \ 2 3 / \ / \ 4 5 6 7
Traversal:
4 5 2 6 7 3 1
Result:
4 5 2 6 7 3 1
20. Postorder C++ Code
void postorder(Node* root) { if (root == nullptr) { return; } postorder(root->left); postorder(root->right); cout << root->data << " "; }
Order:
left ↓ right ↓ root
21. Easy Way to Remember Traversals
This is extremely useful:
PREORDER Root first INORDER Root in the middle POSTORDER Root last
Or:
Preorder → N L R Inorder → L N R Postorder → L R N
The only thing changing is the position of N (Node/Root).
22. Level Order Traversal
Level order visits nodes level by level.
Example:
1 / \ 2 3 / \ / \ 4 5 6 7
Level order:
Level 0 → 1 Level 1 → 2 3 Level 2 → 4 5 6 7
Result:
1 2 3 4 5 6 7
This uses a Queue.
23. Level Order C++
#include <queue> void levelOrder(Node* root) { if (root == nullptr) { return; } queue<Node*> q; q.push(root); while (!q.empty()) { Node* current = q.front(); q.pop(); cout << current->data << " "; if (current->left != nullptr) { q.push(current->left); } if (current->right != nullptr) { q.push(current->right); } } }
Remember:
BFS ↓ Queue ↓ Level Order
24. Complete Traversal Program
Here is a useful program containing all four traversals:
#include <iostream> #include <queue> using namespace std; struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } }; void preorder(Node* root) { if (root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } void postorder(Node* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); cout << root->data << " "; } void levelOrder(Node* root) { if (root == nullptr) return; queue<Node*> q; q.push(root); while (!q.empty()) { Node* current = q.front(); q.pop(); cout << current->data << " "; if (current->left) q.push(current->left); if (current->right) q.push(current->right); } } int main() { 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); root->right->left = new Node(6); root->right->right = new Node(7); cout << "Preorder: "; preorder(root); cout << "\nInorder: "; inorder(root); cout << "\nPostorder: "; postorder(root); cout << "\nLevel Order: "; levelOrder(root); return 0; }
Output:
Preorder: 1 2 4 5 3 6 7 Inorder: 4 2 5 1 6 3 7 Postorder: 4 5 2 6 7 3 1 Level Order: 1 2 3 4 5 6 7
25. Why Are Traversals Important?
Different traversals are useful for different problems.
Preorder
Useful when you want:
Root → Left → Right
It can be useful for copying/serializing a tree and representing its structure.
Inorder
Extremely important for Binary Search Trees.
For a BST:
Inorder → Sorted order
You'll see this in the next topic.
Postorder
Useful when children need to be processed before their parent.
Examples:
- Deleting a tree
- Evaluating expression trees
- Bottom-up calculations
Level Order
Useful for:
- Level-based problems
- Finding nodes at a specific level
- Minimum depth
- BFS problems
- Level averages
26. Height of a Binary Tree
Consider:
1 / \ 2 3 / 4
Height:
1 → 2 → 4
There are 2 edges.
Recursive solution:
int height(Node* root) { if (root == nullptr) { return -1; } return 1 + max( height(root->left), height(root->right) ); }
If you define height in terms of number of nodes instead of edges, the base case and formula are adjusted. Both conventions appear in DSA.
27. Count Nodes
int countNodes(Node* root) { if (root == nullptr) { return 0; } return 1 + countNodes(root->left) + countNodes(root->right); }
For:
1 / \ 2 3 / \ 4 5
Result:
5
The recursive idea is:
Total nodes = 1 current node + left subtree nodes + right subtree nodes
28. Count Leaf Nodes
int countLeaves(Node* root) { if (root == nullptr) { return 0; } if (root->left == nullptr && root->right == nullptr) { return 1; } return countLeaves(root->left) + countLeaves(root->right); }
For:
1 / \ 2 3 / \ / \ 4 5 6 7
Leaf nodes:
4, 5, 6, 7
Result:
4
29. Search in a Binary Tree
A normal binary tree has no ordering rule.
Therefore, to search for a value, we may need to visit every node.
bool search(Node* root, int target) { if (root == nullptr) { return false; } if (root->data == target) { return true; } return search(root->left, target) || search(root->right, target); }
Worst-case:
Time = O(n)
This is an important distinction:
A normal binary tree is not automatically fast for searching.
The special structure that makes searching faster is the Binary Search Tree, which comes next.
30. Maximum Value
You can find the maximum value by recursively checking both subtrees.
int maximum(Node* root) { if (root == nullptr) { return INT_MIN; } int leftMax = maximum(root->left); int rightMax = maximum(root->right); return max(root->data, max(leftMax, rightMax)); }
Because a normal binary tree has no ordering, we generally need to inspect all nodes.
Complexity:
O(n)
31. Diameter of a Binary Tree
The diameter is the longest path between any two nodes.
Example:
1 / \ 2 3 / \ 4 5
One longest path is:
4 → 2 → 1 → 3
Number of edges:
3
The exact implementation is more advanced, but the important idea is:
Diameter is not necessarily a path passing through the root.
For example:
1 / 2 / \ 4 5 / \ 6 7
The longest path can exist entirely inside the left subtree.
32. Maximum Depth
Maximum depth is essentially the maximum distance from root to a leaf.
For:
1 / \ 2 3 / 4
maximum depth:
1 → 2 → 4
If measured as number of nodes:
3
If measured as number of edges:
2
Again, know which convention the problem uses.
33. Recursive Thinking for Binary Trees
This pattern is extremely important.
For almost every recursive tree problem:
1. Handle empty tree 2. Solve left subtree 3. Solve right subtree 4. Combine the answers
For example:
int countNodes(Node* root) { if (root == nullptr) return 0; int left = countNodes(root->left); int right = countNodes(root->right); return 1 + left + right; }
Mental model:
Tree | ┌───────┴───────┐ ↓ ↓ Left subtree Right subtree ↓ ↓ Answer Answer └───────┬───────┘ ↓ Combine
This pattern will appear repeatedly.
34. Binary Tree Complexity
For a binary tree containing n nodes:
| Operation | Complexity |
|---|---|
| Traversal | O(n) |
| Search | O(n) |
| Count nodes | O(n) |
| Find maximum | O(n) |
| Find minimum | O(n) |
| Height | O(n) |
| Level order | O(n) |
Why are these generally O(n)?
Because we may need to visit every node.
35. Traversal Space Complexity
For recursive DFS traversal:
O(h)
where h is the height of the tree.
For a balanced tree:
h ≈ log n
For a skewed tree:
h ≈ n
Therefore recursion can use:
Balanced → O(log n) Skewed → O(n)
The tree's own node storage is separate from the auxiliary recursion space.
36. Binary Tree vs Binary Search Tree
This is very important.
A Binary Tree only says:
At most 2 children
There is no requirement about values.
Example:
10 / \ 50 2
This is a valid binary tree.
But it is not a valid BST.
A Binary Search Tree has an ordering rule:
Left subtree < Root < Right subtree
For example:
10 / \ 5 20 / \ / \ 2 7 15 25
This is a BST.
We'll study this in detail next.
37. Binary Tree vs Heap
A Heap is also a special type of binary tree, usually a complete binary tree with an ordering property.
For a Max Heap:
Parent ≥ Children
Example:
50 / \ 30 40 / \ 10 20
But a heap is not the same thing as a BST.
38. Important Formulas
For a binary tree with height h, where root is at height/depth 0:
Maximum nodes at level h
2^h
Maximum nodes in a tree of height h
2^(h+1) - 1
Minimum nodes for height h
For an unrestricted binary tree:
h + 1
because it can be completely skewed.
Edges
For n nodes:
n - 1
39. Full Binary Tree Formula
For a full binary tree:
Leaves = Internal Nodes + 1
If there are I internal nodes:
L = I + 1
Total nodes:
N = 2I + 1
For example:
Internal nodes = 3 Leaves = 3 + 1 = 4 Total = 2(3) + 1 = 7
Which matches:
1 / \ 2 3 / \ / \ 4 5 6 7
40. Array Representation of Complete Binary Trees
This is very important for the Heap topic later.
A complete binary tree can be stored efficiently in an array.
Consider:
10 / \ 20 30 / \ / \ 40 50 60 70
Array:
[10, 20, 30, 40, 50, 60, 70]
If using 0-based indexing:
Node at index i Left child = 2*i + 1 Right child = 2*i + 2 Parent = (i - 1) / 2
For index 1:
value = 20 left = 2(1)+1 = 3 → 40 right = 2(1)+2 = 4 → 50
This is exactly why complete binary trees are important for heaps.
41. Real-World Applications
Binary trees are used in:
Expression Trees
For:
(2 + 3) * 4
a tree can represent:
* / \ + 4 / \ 2 3
Binary Search Trees
Fast searching and ordered data.
Heaps
Priority queues.
Decision Trees
Machine learning and decision systems.
File and data structures
Hierarchical representation.
42. Common Binary Tree Problems
You should eventually practice:
Beginner
- Preorder
- Inorder
- Postorder
- Level order
- Count nodes
- Count leaves
- Find height
- Find maximum/minimum
- Search a value
Intermediate
- Maximum depth
- Diameter
- Mirror/invert tree
- Check identical trees
- Check balanced tree
- Left/right view
- Top/bottom view
- Zigzag traversal
- Level-wise sums
Advanced
- Lowest Common Ancestor
- Boundary traversal
- Vertical order traversal
- Serialize/deserialize
- Build tree from traversals
- Maximum path sum
🧠 The Most Important Things to Remember
If you're preparing for DSA/interviews, memorize these first:
Binary Tree Definition
Each node has at most 2 children.
Node
struct Node { int data; Node* left; Node* right; };
Traversals
Preorder → Root Left Right Inorder → Left Root Right Postorder → Left Right Root Level → Level by Level
Data structures
DFS → Stack / Recursion BFS → Queue
Complexity
Traversal → O(n) Search → O(n) Height → O(n)
Types
Full Complete Perfect Balanced Skewed
🔥 Final Mental Map
BINARY TREE │ ┌────────────────┼────────────────┐ │ │ │ Structure Traversal Problems │ │ │ ┌─────┼─────┐ ┌───┼────┐ ┌───┼────┐ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Full Complete Perfect Pre In Post Height Diameter │ Level Order │ Queue
And the connection with your previous topics:
Recursion ↓ Binary Tree ↓ DFS ↓ Stack Binary Tree ↓ BFS ↓ Queue Binary Tree ↓ Ordering property ↓ 🌳 Binary Search Tree Binary Tree ↓ Complete + Heap Property ↓ Heap