Ugenz Academy/Tutorial

Binarytree

17 min read3,293 words

Reading progress

Keep learning

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 → Root
  • 20 → Left child of 10
  • 30 → Right child of 10
  • 40, 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:

  1. Every internal node has exactly 2 children.
  2. 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:

OperationComplexity
TraversalO(n)
SearchO(n)
Count nodesO(n)
Find maximumO(n)
Find minimumO(n)
HeightO(n)
Level orderO(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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy