Trace linked structures and trees

A link stores a relationship

A linked list stores a value and a reference to the next node. To insert a node after the current node, preserve the old next reference before replacing it. Losing the reference can make the remainder of the list unreachable from the head.

A binary search tree places smaller keys in the left subtree and larger keys in the right subtree, with an explicit policy for equal keys. Search compares at a node and selects one subtree; it does not scan both when the ordering rule applies.

Distinguish shape from efficiency

An inorder traversal visits the left subtree, the node, and the right subtree. For a valid binary search tree, that yields keys in order. Recursion stops when the subtree is empty. Preorder and postorder choose different positions for the node visit.

A balanced tree can reduce a search to a logarithmic number of levels, but repeated insertions in sorted order can produce a long chain in an unbalanced tree. Explain efficiency using the shape actually produced, rather than assuming all trees are balanced.

Check yourself