Tree traversal [mp]

Micro pattern¶

Description¶

Visit tree nodes in an order determined by when the root is processed relative to its children.

Problems¶

Traversal definitions¶

Choose preorder, inorder, or postorder according to when node work must occur.

• Inorder traversal (DSA)
• Postorder traversal (DSA)
• Preorder traversal (DSA)

Inorder¶

Traverse left, root, then right to process BST keys in ascending order.

• 98. Validate Binary Search Tree (Top Easy)
• 94. Binary Tree Inorder Traversal (Top Medium)
• 230. Kth Smallest Element in a BST (Top Medium)

Preorder¶

Process a root before recursively processing its subtrees.

• 105. Construct Binary Tree from Preorder and Inorder Traversal (Top Medium)
• 297. Serialize and Deserialize Binary Tree (Top Medium)
• 236. Lowest Common Ancestor of a Binary Tree (Top Hard)

Postorder¶

Compute child results before processing their parent.

• 124. Binary Tree Maximum Path Sum (Top Hard)
• 337. House Robber III (Dynamic Programming)

Level traversal through next pointers¶

Use horizontal links to cross each level without a queue.

• 116. Populating Next Right Pointers in Each Node (Top Medium)