Skip to main content

DSAPath9 mincore

Trees

A tree is an acyclic connected graph with a root-child hierarchy when rooted. Trees model nested structure, search decisions, priority queues, parse trees, and recursive subproblems.

Why This Matters

Trees turn nested structure into data. File systems, syntax trees, decision trees, DOM trees, search spaces, and heap arrays all use tree ideas.

Core Idea

A rooted tree has nodes, edges, a root, parents, children, leaves, depth, and height. Traversals define the order of visiting nodes.

TraversalOrder
preordernode, left subtree, right subtree
inorderleft subtree, node, right subtree
postorderleft subtree, right subtree, node
level orderbreadth-first by depth

Worked example: in a binary expression tree for (2 + 3) * 4, postorder traversal produces 2 3 + 4 *, the order used by stack evaluators.

Common Mistakes

  • Assuming every tree is binary. Many trees allow arbitrary branching.
  • Confusing height and depth. Depth is distance from root; height is distance to deepest leaf.
  • Forgetting that unbalanced height can be nn, not log⁡n\log n.

Exercises

  • List preorder, inorder, and postorder for a three-node tree.
  • Explain why recursive tree algorithms need a base case.
  • Draw the tree formed by inserting sorted values into an unbalanced BST.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 12.
  • Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 3.