# 6.1 Binary Trees & Tree Terms

> Root, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.

Chapter: Trees · ~45 min · easy
URL: https://dsa.fetehadin.com/learn/binary-trees

## Mental model

A **family tree** turned upside down. At the top is one ancestor, the **root**. Each person can have children, those children have children, and so on. Unlike a linked list, a tree **branches**: it is **non-linear** and **hierarchical**.

In a **binary tree**, each node has **at most two** children: a **left** and a **right**.

```cpp
struct Node {
    int data;
    Node* left;
    Node* right;
};
```

### The vocabulary

| Term | Meaning |
| --- | --- |
| **Root** | the top node; it has no parent |
| **Parent / child** | a node and the nodes directly below it |
| **Siblings** | children of the same parent |
| **Leaf** | a node with no children |
| **Internal node** | a node with at least one child |
| **Ancestor / descendant** | anything on the path up / down |
| **Subtree** | a node plus all its descendants |
| **Degree** | number of children of a node |
| **Depth** of a node | edges from the root down to it (root depth = 0) |
| **Level** | all nodes at the same depth |
| **Height** of a node | edges on the longest path down to a leaf |
| **Height of the tree** | height of the root |

### Special shapes

- **Full**: every node has **0 or 2** children.
- **Complete**: every level is full **except possibly the last**, which is filled **from the left**. (Heaps in Chapter 8 are complete trees.)
- **Perfect**: every level is completely full. A perfect tree of height h has **2^(h+1) − 1** nodes.

### Thinking recursively

Every tree is "a root plus a left subtree plus a right subtree". So most tree functions look like this:

```cpp
int f(Node* r) {
    if (r == nullptr) return /* base value */;
    return /* combine */ (r, f(r->left), f(r->right));
}
```

## C++ code: binary-tree.cpp

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

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

Node* make(int x, Node* l = nullptr, Node* r = nullptr) { return new Node{x, l, r}; }

int countNodes(Node* r) { return r ? 1 + countNodes(r->left) + countNodes(r->right) : 0; }
int countLeaves(Node* r) {
    if (!r) return 0;
    if (!r->left && !r->right) return 1;
    return countLeaves(r->left) + countLeaves(r->right);
}
int height(Node* r) {                         // edges on the longest root-to-leaf path
    if (!r) return -1;                        // empty tree: -1, single node: 0
    return 1 + max(height(r->left), height(r->right));
}
int depthOf(Node* r, int x, int d = 0) {      // -1 if not found
    if (!r) return -1;
    if (r->data == x) return d;
    int L = depthOf(r->left, x, d + 1);
    return L != -1 ? L : depthOf(r->right, x, d + 1);
}
void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }

int main() {
    //          1
    //        /   \
    //       2     3
    //      / \     \
    //     4   5     6
    //        / \
    //       7   8
    Node* root = make(1, make(2, make(4), make(5, make(7), make(8))), make(3, nullptr, make(6)));
    cout << "nodes:  " << countNodes(root) << "\n";
    cout << "leaves: " << countLeaves(root) << "\n";
    cout << "height: " << height(root) << "\n";
    cout << "depth of 7: " << depthOf(root, 7) << "\n";
    destroy(root);
}
```

Expected output:

```text
nodes:  8
leaves: 4
height: 3
depth of 7: 3
```

## Complexity

| Case | Cost |
| --- | --- |
| count nodes / leaves | O(n): visits every node once |
| height | O(n) |
| find a value (no ordering) | O(n) |

Space: O(h) recursion stack, where h is the height

A binary tree with n nodes has height between ⌊log₂ n⌋ (perfectly balanced) and n − 1 (a straight line). A perfect tree of height h has 2^(h+1) − 1 nodes.

## Videos

- [Binary Tree](https://youtu.be/H5JubkIy_p8) (mycodeschool): Every tree term, plus full/complete/perfect binary trees, with clear drawings.

## Exam lens

Likely questions:

- Define: root, leaf, internal node, sibling, ancestor, descendant, depth, height, level, degree.
- Draw a full, a complete and a perfect binary tree. How do they differ?
- What is the maximum number of nodes at level k? In a binary tree of height h?
- Write recursive functions to count the nodes and compute the height of a binary tree.

Common mistakes:

- Mixing up depth (from the root down to a node) and height (from a node down to its deepest leaf).
- Not stating your height convention. Here, a single node has height 0 and an empty tree −1. Some books count nodes instead of edges.
- Thinking "complete" and "full" mean the same thing.
- Forgetting the `nullptr` base case in recursive tree functions.

## Quick check

1. In the tree on this page (1 at the root, 7 and 8 under 5), what is the depth of node 7?
   A. 1
   B. 2
   C. 3
   D. 4
   Answer: C. Path 1 → 2 → 5 → 7 has 3 edges.

2. A node with no children is a…
   A. root
   B. leaf
   C. sibling
   D. internal node
   Answer: B. Leaves sit at the bottom. Nodes with at least one child are internal.

3. Maximum number of nodes in a binary tree of height 3?
   A. 7
   B. 8
   C. 15
   D. 16
   Answer: C. 2^(3+1) − 1 = 15, which is a perfect tree with levels of 1, 2, 4 and 8 nodes.

4. A complete binary tree is one where…
   A. every node has 0 or 2 children
   B. every level is full except possibly the last, filled from the left
   C. all leaves are at the same depth
   D. it is sorted
   Answer: B. "0 or 2 children" is full. "All levels completely full" is perfect.

## Practice

**Trace by hand.** Draw the tree: A has children B, C. B has D, E. C has right child F. E has left child G. List leaves, internal nodes, the height of the tree, the depth of G, and the siblings of D.

Solution:

- Leaves: D, G, F
- Internal: A, B, C, E
- Height: 3 (A → B → E → G)
- Depth of G: 3
- Sibling of D: E


**Implement it.** Write `int countInternal(Node* r)` and `int sumAll(Node* r)`, and `bool isFull(Node* r)` (every node has 0 or 2 children).

Hint: Each one is "handle nullptr, handle this node, recurse on left and right". For isFull: a node with exactly one child returns false.

```cpp
bool isFull(Node* r) {
    if (!r) return true;
    if (!r->left != !r->right) return false;   // exactly one child
    return isFull(r->left) && isFull(r->right);
}
```


**Problems:**

- [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/) (easy). Hint: Like `height()`, but LeetCode counts nodes, so return 0 for nullptr.
- [Same Tree](https://leetcode.com/problems/same-tree/) (easy). Hint: Both null → true; one null → false; else compare values and recurse on both sides.
- [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) (easy). Hint: Swap left and right, then recurse on both.

## Mastery checklist

- [ ] I can define every tree term and point to it on a drawing.
- [ ] I can tell full, complete and perfect binary trees apart.
- [ ] I can write recursive count, leaves and height functions.
- [ ] I can compute the maximum number of nodes for a given height.