Model answer
Induct on n. A one-node tree has zero edges; adding a new node while preserving a tree requires exactly one edge to an existing node, so an n-node tree has (n−2)+1=n−1 edges.
Use the key terms, then explain the reasoning.
Trees & Applications
C++17
C++17Tree Fundamentals
Trees model hierarchical relationships with nodes, edges, a root, parent-child links, depth, height, and subtrees.
Open this in the visual labWhat to understand
- Terminology
- Binary tree properties
- Full, complete, perfect, and balanced trees
- Recursive structure
Remember this
- 1A tree with n nodes has n−1 edges
- 2Height controls many operation costs
- 3A subtree is itself a tree
Detailed notes
A tree is a connected acyclic hierarchy. The unique path between any two nodes makes recursive parent-child decomposition possible, while choosing a root gives depth, ancestor, descendant, and subtree relationships.
Binary trees limit each node to left and right children. Shape terms are distinct: full concerns child count, complete concerns level filling, perfect fills every level, and balanced bounds height relative to node count.
How it works
- 1Identify root, edges, leaves, and internal nodes.
- 2Compute depth downward from the root and height upward from leaves.
- 3Use recursive definitions for size, height, and subtree properties.
- 4Relate maximum nodes at level d to 2^d.
Where it is used
- File and organisational hierarchies
- Expression and syntax representation
- Search, priority, and decision structures
Common mistakes
- Confusing node depth with tree height
- Using complete, full, and perfect interchangeably
- Forgetting that an empty tree needs a defined height convention
Implementation perspective
This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.
Exam & viva
Open a prompt when you are ready to check your answer.