Concept
Tree represents the nodes connected by edges. It is a non-linear data structure. One node is marked as Root node. Every node other than the root is associated with one parent node. Each node can have an arbitrary number of child nodes.
Features of Trees
- Root node is the top most node. A tree can contain only one root node.
- If we have N nodes in a tree, then we will have N-1 edges/Links
- Every child will have only one parent but a parent can have multiple child
- Tree is a recursive data structure
Tree Terminology
Degree of a Node: the total number of children
Degree of a Tree: the highest degree of a particular node among all the nodes of a tree.
Leaf node = external node=terminal node
Level of tree: each step from top to bottom in a tree is called as level. Levels starts from 0.
Height of node: The total number of edges length in the longest path from any leaf node to the desired node.
Height of Tree: total number of edges along with the longest path from any leaf node to the root node.
Depth of node: distance between root node to required node.
Depth of Tree: total number of edges in the longest path from the root to any leaf.
Depth of root= height of the leaf =0
Types of Trees
- General Tree: a node can contain 0 to any number of children
- Binary Tree: a node can contain 0(min) to 2(max) number of children only.
Types of Binary Trees
- Full Binary Tree
- Complete BT
- Perfect BT
- Balanced BT
- Pathological BT
Full Binary Tree: Every node can have 0 or 2 child nodes but not 1 child node
Complete BT: All levels except the last level are completely filled. Last level can be either completely filled or filled from left to right.
Perfect BT: All internal nodes have 2 child nodes and all leaf nodes present in the same level.
Balanced BT: it is also known as Height-balanced Binary Tree. In this tree, height of the left sub tree and height of right sub tree differs by 1 for every node. The difference can be less than 1 but cannot be greater than 1.
Balance of a Node= |height of left sub tree – height of right sub tree|
Height of tree = height of the root node
Height of empty tree = -1
Pathological Binary Tree: It is also known as Degenerate Binary tree. In this tree, every parent node has only one child node.
Binary Search Tree (BST): This is also called as ordered or sorted binary tree.
BST is a special type of binary tree with the following properties:
- The left subtree of a node contains only nodes with keys lesser than node’s key
- The right subtree of a node contains only nodes with keys greater than node’s key
- The left subtree and right subtree each must also be a BST
Key = data= value
Since BST is ordered data structure, it is useful in Searching or Sorting Algorithms.
Exercise)
Create BST with the following data:
5,4,10,7,25,36,1,121
Types of Tree Traversals
In Order
Pre Order
Post Order
Level Order
Traversal is a process of visiting all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree.
Depth-First Traversal:
In-order Traversal
Pre-order Traversal
Post-order Traversal
Breadth-First Traversal or Level order
In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.
Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node