# introduction to trees

Tree is a hierarchical data structure which stores the information naturally in the form of hierarchy style.

Each node is connected to a number of nodes with the help of pointers (edges).

It is a non-linear data structure compared to arrays, linked lists, stack and queue.

**Root**:Root is a special node in a tree. The entire tree is referenced through it. It does not have a parent.

**Parent Node**:Parent node is an immediate predecessor of a node.

**Child Node**:All immediate successors of a node are its children.

**Siblings**:Nodes with the same parent are called Siblings.

**Path**:Path is a number of successive edges from source node to destination node.

**Height of Node**:Height of a node represents the number of edges on the longest path between that node and a leaf.

**Height of Tree**: Height of tree represents the height of its root node.

**Depth of Node**:Depth of a node represents the number of edges from the tree's root node to the node.

**Degree of Node**:Degree of a node represents a number of children of a node.

**Edge**:Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf.

### ** Binary Tree**

A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child or 2 child nodes.

**Properties of a Binary Tree:**

**Types of Binary Trees: **

**Full Binary Tree:**A Binary Tree is full if every node has either 0 or 2 children. The following are examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children.

**Complete Binary Tree:**A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

**Perfect Binary Tree:**A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.