# Discuss Binary Trees in detail?

Binary Tree has at most 2 children nodes. Since each element in a binary tree can have only 2 children, we name them the left and right child. It includes the following parts -

• Data
• Pointer to the left child
• Pointer to the right child

There are 3 traversal methods that are very important from an interview point of view.

1. PreOrder Traversal: root – left child – right child. It means that the root node is traversed first then its left child and finally the right child.

2. InOrder Traversal: left child – root – right child. It means that the left child is traversed first then its root node and finally the right child.

3. PostOrder Traversal: left child – right child – root. It means that the left child is traversed first then the right child and finally its root node.

CODE -

``````#include <stdlib.h>

#include <iostream>

using namespace std;

struct node {
int data;
struct node *left;
struct node *right;
};

// New node creation
struct node *newNode(int data) {
struct node *node = (struct node *)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;
node->right = NULL;
return (node);
}

// Traverse Preorder
void traversePreOrder(struct node *temp) {
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}

// Traverse Inorder
void traverseInOrder(struct node *temp) {
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}

// Traverse Postorder
void traversePostOrder(struct node *temp) {
if (temp != NULL) {
traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}

int main() {
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);

cout << "preorder traversal: ";
traversePreOrder(root);
cout << "\nInorder traversal: ";
traverseInOrder(root);
cout << "\nPostorder traversal: ";
traversePostOrder(root);
}
``````

Applications of Binary Trees are:-