Tree
- A tree is a nonlinear data structure in which items are arranged in a sorted Sequence, It is used to represent hierarchical relationships existing among several data items. Each node of a tree may or may not point to more than one node.
- It is a finite set of one or more data items (nodes) such that there is a special data item called the root. Its remaining data items are portioned into no. of mutually exclusive subsets, each of which is itself a tree, and they are called subtrees.
- It represents nodes connected by the edges.:
 |
| TREE |
Tree terminology:
Root: - The first node in a hierarchical arrangement of data items is the root.
Note: - Each data item in a tree is called a node.
Degree of a node: - It is the no. of subtrees of a node in a given tree from fig. Here,
- Degree of node A = 2
- Degree of node D = 2
- Degree of node F = 0
Degree of a tree: - It is the maximum degree of nodes in a given tree here degree of the tree is 2.
Terminal node / Leaf node: - A node with a degree of 0 is a terminal node.
Non-terminal node / Parent Node: - Any node except the root whose degree is not zero is called a non-terminal node.
Keys: - it represents a value of a node based on which a search operation is to be carried out for a node.
Siblings: - The children nodes of given parent nodes are called siblings. F and G are siblings of parent node C & so on.
Edge: - It is a connecting line of two nodes i.e. line drawn from one node to another.
Path: - It is a sequence of consecutive edges from the source node to the destination node.
Traversing: -It means passing through the nodes in a certain order.
Level: - The entire tree structure is leveled in such a way that the root ridden is always at level zero. Then its immediate children are at level 1 and their immediate children are at level 2 and so on up to the terminal nodes. Here, the level of a tree is 3.
 |
| Levels Of Tree |
Depth or height: - The height of a node represents the number of edges on the longest path between that node and the leaf node.
The depth of a node represents the number of edges from the tree’s root node to the node. It is the maximum label of any node in a given tree here, the depth of a tree is 3.
Binary tree:
A binary tree is a finite set of data items that is either empty or consists of a single item called the root and two disjoint binary trees the left subtree and right subtree. In the binary tree, the maximum degree of any node is at most 2 i.e. each node has a 0, 1, or 2-degree node.
 |
| Binary Tree |
Properties of Binary Tree:
- The maximum number of nodes at level ‘l’ of a binary tree is 2l.
- The maximum number of nodes in a binary tree of height ‘is 2h – 1.
- In a Binary Tree with N nodes, the minimum possible height or the minimum number of levels is Log2(N+1).
- Binary Tree with L leaves has at least | Log2L |+ 1 level.
- In a Binary tree where every node has 0 or 2 children, the number of leaf nodes is always one more than nodes with two children.
Full Binary Tree:
A Binary Tree is a full binary tree if every node has 0 or 2 children.
Complete Binary Tree:
A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible.
 |
| Complete Binary Tree |
Perfect Binary Tree:
A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.
 |
| Perfect Binary Tree |
Binary search tree:
A binary search tree is a node-based binary tree in which each node has a value greater than every node of left subtree and less than every node of right subtree which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
 |
| Binary Search Tree |