### Topics covered in this snack-sized chapter:

Trees are flexible, powerful non-linear data structure that can be used to represent data items which has hierarchical relationship.
Tree is an ideal data structure for representing hierarchical data.
Tree can be defined as a finite set of one or more data items (i.e. nodes) such that:
- There is a special node called the root of the tree.

- The remaining nodes are partitioned into n disjointed set of nodes each of which is a subtree.

A node is a structure which may contain a value, a condition, or represent a separate data structure.
Each node in a tree has zero or more child nodes.

A node that has a child is called the child's parent node.

Nodes that do not have any children.

The topmost node in a tree.

Any node which is neither a root, nor a leaf is
called an interior node.

Any node higher up than the parent is called an ancestor node.

The height of a tree is defined to be the length of the longest path from the root to a leaf in that tree (including the path to root).

The length of the path to its root.

In the above represented tree:
- The root node at the top, has no parent.

- The node labeled 51 has two children labeled 13 and 17 and one parent labeled 91;

- Node labeled 17, 12, 2 & 4 are leaf nodes.

- 13, 51 and 42 are interior nodes.

Every node in a binary tree can have at most two children.
The two children of each node are called the left child and right child corresponding to their positions.
A node can have only a left child or only a right child or it can have no children at all. (It can have two children as well)
Left child is always less than its parent, while right child is greater than its parent.

struct tree_node{
int data;
struct tree_node *left_child;
struct tree_node *right_child;
};

A tree is called complete binary tree if each of its nodes has two children, except the last (leaf) nodes.
In other words, every non-terminal node of it must have both children except the leaf nodes.
So, at any level the maximum number of nodes is equal to 2^{(Level no.)
}. (Maximum number is of nodes at a level is 2^(level no.), i.e. if level is 0 no. of node is 2^0=1 which is our root node. )
At level 0, there must be only one node and that is the root node. A at level 1 the maximum nodes must be 2. At level 3 the maximum nodes must be equal to 8.

When every non-leaf node in binary tree is filled with left and right sub-trees, the tree is called strictly binary tree.

When every node of a tree has either 0 or 2 children then such a tree is called extended binary tree or 2-tree.

A Binary Search Tree is a binary tree with the following properties:
- All items in the left subtree are less than the root.

- All items in the right subtree are greater or equal to the root.

- Each subtree is itself a binary search tree.

Binary search trees provide an excellent structure for searching a list and at the same time for inserting and deleting data into the list.

In a binary search tree,
- The left subtree contains key values less than the root.

- The right subtree contains key values greater than or equal to the root.

###### Traversal in Binary Search Tree:

Preorder
Inorder
Postorder
- These names are chosen according to the sequence in which the root node and its children are visited.

- Suppose there are only 3 nodes in the tree having the following arrangement:

Algorithm:
void preorder(struct tree_node * p){ if(p!=NULL){
printf(“%d\n”, p->data);
preorder(p->left_child);
preorder(p->right_child);
}
}

##### Example:

Preorder: a b c d f g e

##### Note:

Preorder traversal is also used to get prefix expression on of an expression tree.

Algorithm:
void inorder(struct tree_node *p) { if(p!=NULL){
inorder(p->left_child);
printf(“%d\n”, p->data);
inorder(p->right_child);
}
}

##### Example:

Inorder: bafdgce

##### Note:

In case of Binary Search tree, inorder traversal gives nodes in increasing order.

Algorithm:
void postorder(struct tree_node *p) { if(p!=NULL){
postorder(p->left_child);
postorder(p->right_child);
printf(“%d\n”, p->data);
}
}

##### Example:

Postorder: bfgdeca

##### Node:

Postorder traversal is also useful to get the postfix expression of an expression tree.