Trees : non linear data structure: Basic Terminology and introduction

Trees: Linked Lists, stacks, and queues, are all linear structures:
In Linked Lists, stacks, and queues, one item follows another.
But Trees are non-linear structure:

• More than one item can follow another.
• The number of items that follow can vary from one item to another.

Trees have many uses:

• representing family trees
• represents hierarchical relationship

Here is the conceptual picture of a tree (of letters):

• each letter represents one node
• the lines drawn from one node to another are called edges
• the topmost node is the root (node A)
• the bottom nodes  are the leaves (nodes D, E, F)
• E and F are siblings as they have a common parent i.e, C . (B,I,C are also siblings)

A path is  sequence of (zero or more) connected nodes; for example, here are 2 of the paths in the tree shown below

The length of a path is the number of nodes in the path, e.g.:
in A->B->D in the above figure, the length of the path is 2
and in C->E , the length of the path is 1

The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.  

The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0
















 Given two connected nodes like this:

Node A is called the parent, and node B is called the child.
The descendants of a node n are all nodes reachable from n (n's children, its children's children, etc.).

  

 A subtree of a given node includes one of its children and all of that child's descendants.

Degree of a node:  is the number of children the node has. Leaf nodes has zero degree

Degree of a tree is the maximum degree  a node has in the tree.

The entire tree is levelled in such a way that the root node is at level 0, then its immediate childres are at level1 and so on

Binary tree: is a tree in which each node has 0 ,1 or 2 children.

Types of binary tree:

1. Full binary tree: degree of every node is 2 except the leaf node and all the leaf nodes must be at same level.

2. complete binary tree: A complete binary tree is a binary tree in which every level, except possibly the last level is completely filled and the filling is done in the order of root, left, right. Root is filled first and then its left child and then its right child and so on.

Tree traversals:

1. inorder : left, root, right

2. preorder: root, left , right

3. post order: left, right, root

Q) draw all possible binary trees with 3 nodes.

Q) draw all possible binary trees with 4 nodes: