Discuss Binary Trees in detail?

Software Development
#1

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:-

  • For easy and quick access to data
  • In router algorithms
  • To construct or build a heap
  • Syntax tree