DataslopeTrees and Binary Trees
Learn tree terminology, binary-tree storage, traversals, and recursive tree properties in C++
A tree is a connected acyclic graph. In a rooted tree, one node is the root, every non-root node has a parent, and edges lead from parent to child.
Tree vocabulary
- The root is the top node.
- A leaf has no children.
- Depth counts edges from the root to a node.
- Height measures the longest downward path. Many coding problems define maximum depth as a number of nodes.
- A level contains all nodes at the same depth.
General trees vs binary trees
A general tree node can have any number of children. A binary tree node has at most two children, usually called left and right.
Binary tree representations
A linked representation is flexible and works well for sparse trees.
Complete binary trees are often stored in arrays. For index i, the left child is 2*i + 1, the right child is 2*i + 2, and the parent is (i - 1) / 2.
Arrays are best for complete trees
The array formulas are perfect for heaps. Sparse trees waste many array positions, so linked nodes are usually better there.
Depth-first traversals
Pre-order visits root, left, right. In-order visits left, root, right. Post-order visits left, right, root.
For this tree:
- Pre-order:
1 2 4 5 3 - In-order:
4 2 5 1 3 - Post-order:
4 5 2 3 1
Level-order traversal
Level-order is breadth-first search. A queue processes nodes one level at a time.
Iterative in-order traversal
The recursion stack can be simulated with std::stack.
Calculating tree properties
Most tree properties are naturally recursive: solve the left subtree, solve the right subtree, then combine the answers.
Practice: Sum of all node values
Implement int sumTree(TreeNode* root). The driver builds a binary tree and prints the sum of all values.
Practice: Maximum depth of binary tree
Implement int maxDepth(TreeNode* root). Count nodes on the longest root-to-leaf path.
Practice: Level-order traversal
Return the tree values grouped by level as std::vector<std::vector<int>>. The driver prints each level on its own line.
Check your understanding
Which statement best defines a leaf in a rooted tree?
The node with the largest value
The root node only
A node with no children
Any node at depth one
For a binary tree with root 1, left child 2, and right child 3, what is pre-order traversal?
2 1 3
1 2 3
2 3 1
3 1 2
When is array representation usually better than linked nodes for a binary tree?
When the tree is very sparse
When the tree is complete or nearly complete
When every node needs a parent pointer
When traversal must be recursive