Section 10: Tree Recursion, Traversals, and Iterators (109–120)

Recursive calculation of binary tree size

$1 + \text{size}(\text{left}) + \text{size}(\text{right})$, where an empty tree has a base size of $0$.

Recursive calculation of binary tree height

$1 + \max(\text{height}(\text{left}), \text{height}(\text{right}))$, relative to the base height of an empty tree.

Time complexity of recursive binary tree size calculation

$O(n)$, because every node in the tree must be visited.

Time complexity of recursive binary tree height calculation

$O(n)$, because every node in the tree may need to be visited.

Auxiliary space complexity of recursive binary tree traversal

$O(h)$, where $h$ is the tree height, due to the call stack frames allocated during recursion.

Order of nodes visited in a preorder traversal

$$\text{Root} \rightarrow \text{Left} \rightarrow \text{Right}$$

Order of nodes visited in an inorder traversal

$$\text{Left} \rightarrow \text{Root} \rightarrow \text{Right}$$

Order of nodes visited in a postorder traversal

$$\text{Left} \rightarrow \text{Right} \rightarrow \text{Root}$$

Preorder iterator stack mechanism

Pop and visit the top node, then push its right child followed by its left child onto the stack.

Reason a preorder iterator pushes the right child before the left child

Because a stack operates as last-in, first-out (LIFO), pushing the right child first ensures the left child is popped and processed next.

How an inorder iterator prepares the next node

Pushes nodes onto the stack while traversing down the left subtree until reaching a node without a left child.

Inorder iterator procedure after popping and visiting a node

If the popped node has a right subtree, move to that right child and cascade down its leftmost path, pushing each node encountered onto the stack.

Decision rule for exploring a right subtree in a postorder iterator

After popping a node, check the parent node on top of the stack; if the popped node was the parent's left child, traverse and process the parent's right subtree before visiting the parent.

Function of next() in a binary tree iterator

Returns the next element according to the chosen traversal order and updates the iterator's internal state.