How is a general tree stored with linked nodes?

Question

Accepted Answer

Each node is an object with three references: to its element, to its parent, and to a sequence of its children. The nodes implement the Position ADT.
The children cannot be stored as a fixed set of fields, because a node in a general tree can have any number of them. So each node keeps a list (sequence) of child references, which can grow and shrink.

Field
Points to

element
the stored data

parent
the parent node (null for the root)

children
a sequence of references to the child nodes

What each field makes cheap:

parent makes parent(p) and the upward walk of depth $O(1)$ per step.
children makes children(p) and numChildren(p) direct, which is what every downward algorithm (height, traversals) needs.

Because the nodes implement the Position ADT, a node object can be handed out as the "position" through which callers reach the element, and the tree's operations take it back as an argument.

Field	Points to
element	the stored data
parent	the parent node (`null` for the root)
children	a sequence of references to the child nodes