**Tree**:- 1.
- A single node is a tree and this node is the root of the tree.
- 2.
- Suppose
*r*is a node and*T*_{1},*T*_{2},...,*T*_{k}are trees with roots*r*_{1},*r*_{2},...,*r*_{k}, respectively, then we can construct a new tree whose root is*r*and*T*_{1},*T*_{2},...,*T*_{k}are the subtrees of the root. The nodes*r*_{1},*r*_{2},...,*r*_{k}are called the children of*r*.

See Figure 4.1. Often, it is convenient to include among trees, the

**null**tree, which is a tree with no nodes.**Path**A sequence of nodes

*n*_{1},*n*_{2},...,*n*_{k}, such that*n*_{i}is the parent of*n*_{i + 1}for*i*= 1, 2,...,*k*- 1. The length of a path is 1 less than the number of nodes on the path. Thus there is a path of length zero from a node to itself.**Siblings**The children of a node are called siblings of each other.

**Ancestor and Descendent**If there is a path from node

*a*to node*b*, then*a*is called an**ancestor**of*b**b*is called a**descendent**of*a*If

*a**b*, then*a*is a proper ancestor and*b*is a proper descendent.**Subtree**A subtree of a tree is a node in that tree together with all its descendents.

**Height**The height of a node in a tree is the length of a longest path from the node to a leaf. The height of a tree is the height of its root.

**Depth**The depth of a node is the length of the unique path from the root to the node.

**Tree Traversal**This is a systematic way of ordering the nodes of a tree. There are three popular schemes (many other schemes are possible):

- 1.
- Preorder
- 2.
- Inorder
- 3.
- Postorder

All these are recursive ways of listing or visiting all the nodes (each node exactly once)