Trees

Lesson 8 · OKSTEM College · AS Computer Science

Rooted Trees & Terminology

A rooted tree designates one vertex as the root. Every other vertex has a unique parent, and nodes with no children are leaves.

Term	Definition
Root	Top node; no parent
Child / Parent	Directed edge from parent down to child
Leaf	Node with no children
Height	Longest path from root to any leaf
Level of node v	Distance from root to v
Subtree	A node plus all its descendants

Binary Trees & Search Trees

A binary tree: each node has at most 2 children (left, right). A Binary Search Tree (BST): all values in the left subtree < node < all values in the right subtree.

Full binary tree: every node has 0 or 2 children Complete binary tree: all levels full except possibly the last BST property: inorder traversal (Left\toRoot\toRight) gives sorted output Search: O(log n) average, O(n) worst case (degenerate/skewed tree)

Tree Traversals

Preorder (Root → Left → Right): used to copy a tree or produce prefix expressions.

Inorder (Left → Root → Right): gives sorted order in a BST.

Postorder (Left → Right → Root): used for deletion, postfix expressions.

Level-order (BFS): visit all nodes level by level — uses a queue.

Spanning Trees & Minimum Spanning Trees

A spanning tree of a connected graph uses all vertices with the minimum possible edges (n−1). A minimum spanning tree (MST) minimises total edge weight — solved by Kruskal’s or Prim’s algorithm.

Applications: MSTs appear in network cabling (minimum wire), road planning, cluster analysis, and circuit board layout.

Practice Problems

1. A full binary tree has 15 nodes. How many leaves does it have?

A full binary tree with n internal nodes has n+1 leaves. For 15 total nodes: 7 internal + 8 leaves. (Or use: leaves = (n+1)/2 = 8 for a perfect binary tree of height 3.)

2. List the inorder traversal of: root=4, left=2, right=6, 2's children=1,3, 6's children=5,7.

Inorder (L → Root → R): 1, 2, 3, 4, 5, 6, 7.
This is sorted order — confirming it's a valid BST.

Knowledge Check

In a rooted tree, a leaf node is defined as

Trees don't inherently have numeric values; leaves are structural.

Correct — leaves are terminal nodes with degree 1 (in the rooted sense, no children).

The root has no parent; leaves have no children.

Level 2 nodes may or may not have children.

Recap: leaf = no children. Root = no parent. Internal node = has at least one child.

Inorder traversal of a BST produces

BST inorder is deterministic and sorted.

Correct — BST property guarantees Left < Root < Right, so inorder = sorted.

That's not inorder; it's neither a standard traversal.

Inorder visits every node, not just leaves.

Recap: BST + inorder (L→Root→R) = sorted output. This is why BSTs are used for sorted data structures.

BST search has worst-case time complexity

O(log n) is the average/balanced case; worst case is different.

Correct — if items are inserted in sorted order, the BST degenerates to a linked list.

O(1) would require direct addressing; BST search follows a path.

That's typical sorting complexity, not BST search.

Recap: balanced BST → O(log n). Skewed/degenerate BST → O(n). Balanced BSTs (AVL, Red-Black) guarantee O(log n).

A spanning tree of a graph with n vertices has

n edges in a connected graph would create one cycle.

Correct — spanning tree = all vertices, minimum edges = n−1, no cycles.

n² far exceeds a tree; that's closer to a dense graph.

A spanning tree uses a subset of edges, not all of them (unless the graph is itself a tree).

Recap: any spanning tree on n vertices has exactly n−1 edges. MST finds the spanning tree with minimum total weight.

Preorder traversal visits nodes in the order

That's inorder.

Correct — preorder visits the root before its subtrees.

That's postorder.

Level-by-level is BFS / level-order traversal.

Recap: Pre = Root first. In = Root middle. Post = Root last. Remember: pre/in/post refers to WHEN the root is visited relative to its subtrees.

← Previous Next →