Tree

A general tree is a tree where each node may have zero or more children (a binary tree is a specialized case of a general tree). General trees are used to model applications such as file systems.

A general tree consists of a node called the root node which can have any number of children nodes attached to it, children nodes can in turn have their own children nodes attached to them.

The root node is on the top layer call it layer 0 or 1 and it’s children are on the level below it, in order to traverse a tree you’ll have to traverse from top to bottom i.e. if you want to access a specific node you’ll have to traverse from the top of the tree up to that node.

A Leaf Node is a node which has no children. A general tree looks like this

A general tree is a data structure with nodes. There is no limit on the degree of nodes in a general tree, and each node can have an infinite number of children.

Real life examples of general trees:

Implementation of General Tree

Since each node in a tree can have an arbitrary number of children, and that number is not known in advance, the general tree can be implemented using a first child/next sibling method.

Each node will have TWO pointers: one to the leftmost child, and one to the rightmost sibling.