Solve problems that are commonly asked in C++ coding interviews related to common data structures.

Ace the C++ Coding Interview

Data structures are among the fundamentals of computer science and are often a core decision in developing efficient programs. They are categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This module contains a detailed review of common data structures in C++. We'll also become well-equipped with different data structures by implementing them.
By the end of this module, we'll have expertise in solving problems in data structures.

Data Structures

# Introduction

In this traversal, the elements are traversed in the `root-left-right` order. We first visit the root/parent node, then the left child, and then the right child. Here is a high-level description of the algorithm for *Pre-Order* traversal, starting  from the root node:

1. Visit the current node, i.e., print the value stored at the node

2. Call the ```preOrderPrint()``` function on the left sub-tree of the `current node`.

3. Call the ```preOrderPrint()``` function on the right sub-tree of the `current node`.


void preOrderPrint(Node* currentNode) {
    if(currentNode!=NULL) {
        cout<<currentNode->value<<endl;
        preOrderPrint(currentNode->leftChild);
        preOrderPrint(currentNode->rightChild);
    }

}

#include <iostream>

using namespace std;

class Node {
  public:
    int value;
    Node * leftChild;
    Node * rightChild;
    Node();
    Node(int val);
};

class BinarySearchTree {
  private:
    Node * root;
  public:
    BinarySearchTree();
    BinarySearchTree(int rootValue);
    Node * getRoot();
    Node * insert(Node* currentNode, int val);
    void insertBST(int val);
    void preOrderPrint(Node* currentNode);    
};

#include "BST.h"

Node::Node() {
  value = 0;
  leftChild = NULL;
  rightChild = NULL;
}

Node::Node(int val) {
  value = val;
  leftChild = NULL;
  rightChild = NULL;
}

BinarySearchTree::BinarySearchTree() {
  root = NULL;
}

BinarySearchTree::BinarySearchTree(int rootValue) {
  root = new Node(rootValue);
}

Node * BinarySearchTree::getRoot() {
  return root;
}

Node * BinarySearchTree::insert(Node * currentNode, int val) {
  if (currentNode == NULL) {
    return new Node(val);
  }
  else if (currentNode -> value > val) {
    currentNode -> leftChild = insert(currentNode -> leftChild, val);
  } 
  else {
    currentNode -> rightChild = insert(currentNode -> rightChild, val);
  }

  return currentNode;
}

void BinarySearchTree::insertBST(int value) {
  if (getRoot() == NULL) {
    root = new Node(value);
    return;
  }
  insert(this -> getRoot(), value);
}

void BinarySearchTree::preOrderPrint(Node * currentNode) {
  if (currentNode != NULL) {
    cout << currentNode -> value << endl;
    preOrderPrint(currentNode -> leftChild);
    preOrderPrint(currentNode -> rightChild);
  }
}

#include "BST.h"

int main() {

    BinarySearchTree BST(6);
    BST.insertBST(4);
    BST.insertBST(9);
    BST.insertBST(5);
    BST.insertBST(2);
    BST.insertBST(8);
    BST.insertBST(12);

    cout << "PreOrder Print" << endl;
    BST.preOrderPrint(BST.getRoot());

    return 0;
}

runBST

## Explanation

First, we create an object of the `BinarySearchTree` class and insert some values into it. We will then pass the tree's root to the ```preOrderPrint()``` function. If the given node is *not* `NULL`, this function prints the value at the node and calls `preOrderPrint()` on the left child first and then on the right child. 

If you run the code for the BST given above, it will print out the following output:

$$[6,4,2,5,9,8,12]
$$

## Time Complexity
This is a linear-time algorithm, i.e., the time complexity of it is in $O(n)$ because a total of $n$ recursive calls occur. 

----

If you have understood Pre-Order Traversal clearly, it will be a piece of cake for you to understand the rest of the traversals as all three of them are similar to one another. 

In this lesson, we will cover the traversal strategy, 'Pre-Order Traversal' in a Binary Search Tree, and implement it in C++.