Binary tree is non-linear data structure in which each node has at most two children, which are referred to as the left child and the right child , while Simple tree can have any number of children.
-
Node: A single element in a tree.
-
Root: The topmost node in a tree.
-
Parent: A node that has child nodes.
-
Child: A node that has a parent node.
-
Leaf: A node that has no children.
-
Sibling: Nodes that share the same parent.
-
Ancestor: A node that is on the path from the root to a given node.
-
Descendant: A node that is on the path from a given node to a leaf.
-
Depth: The number of edges on the path from the root to a given node.
-
Height : The number of Nodes on the longest path from a given node to a leaf.
-
Level: The set of all nodes at a given depth.
-
Subtree: A tree that is a descendant of a given node.
-
Diameter: The number of nodes on the longest path between two leaves in the tree.
-
Balanced Tree : A tree is balanced if the height of the left and right subtrees of every node differ by at most 1.
-
Isomorphic : Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.
class Node{
public:
int data;
Node* left;
Node* right;
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};
Node* CreateBinaryTree(Node* root){
int data;
cout<<"Enter data : ";
cin>>data;
if(data == -1){
return NULL;
}
root = new Node(data);
cout<<"Enter left child of "<<data<<" : ";
root->left = CreateBinaryTree(root->left);
cout<<"Enter right child of "<<data<<" : ";
root->right = CreateBinaryTree(root->right);
return root;
}
void LevelOrderTraversal(Node* root){
if(root == NULL){
return;
}
queue<Node*> q;
q.push(root);
q.push(NULL);
while(!q.empty()){
Node* current = q.front();
if(current == NULL){
cout<<endl;
q.pop();
if(!q.empty()){
q.push(NULL);
}
}
cout<<current->data<<" ";
if(current->left != NULL){
q.push(current->left);
}
if(current->right != NULL){
q.push(current->right);
}
q.pop();
}
}
int main(){
Node* root = NULL;
root = CreateBinaryTree(root);
cout<<endl;
LevelOrderTraversal(root);
return 0;
}
-
1. Inorder Traversal : In this traversal, the nodes are recursively visited in this order: left, root, right.
- Example : Inorder traversal of 1 2 -1 4 -1 -1 3 -1 -1 is 4 2 1 3 is 4 2 1 3
-
2. Preorder Traversal : In this traversal, the nodes are recursively visited in this order: root, left, right.
- Example : Preorder traversal of 1 2 -1 4 -1 -1 3 -1 -1 is 1 2 4 3
-
3. Postorder Traversal : In this traversal, the nodes are recursively visited in this order: left, right, root.
- Example : Postorder traversal of 1 2 -1 4 -1 -1 3 -1 -1 is 4 2 3 1
Important : Postorder traversal is used to delete the tree , AND PostOrder Traversal is Reverse of PreOrder Traversal with only difference that right child is visited/appended before left child.