# Chapter 6 : Trees

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

#### Tree arrow_upward

• 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.

#### Tree Terminologies arrow_upward

###### Node:

• 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.

• ###### Parent Node:

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

• ###### Leaf Nodes:

• Nodes that do not have any children.

• ###### Root Node:

• The topmost node in a tree.

• ###### Interior Node:

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

• ###### Ancestor Node:

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

• ###### Height:

• 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).

• ###### Depth of node:

• 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.

#### Binary Tree arrow_upward

• 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;
};
```

#### Complete Binary Tree arrow_upward

• 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.

• #### Strictly Binary Tree arrow_upward

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

• #### Extended Binary Tree arrow_upward

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

• #### Binary Search Tree arrow_upward

• 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.

• ###### Basic Property:

• 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:
•  In–order: n2 n1 n3
•  Pre-order: n1 n2 n3
•  Post order: n2 n3 n1

###### Preorder Traversal:

• 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.

• ###### Inorder Traversal:

• 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.

• ###### Postorder Traversal:

• 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.

• #### Thank You from Kimavi arrow_upward

• Please email us at Admin@Kimavi.com and help us improve this tutorial.

• Kimavi - A Video Learning Library { Learning is Earning }

Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only \$10 a month