Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Pre-Order Traversal

Understand pre-order traversal by exploring how to visit nodes in a binary tree in root-left-right order. Learn its implementation in C++, including recursive function calls and time complexity. This lesson helps build a foundation for other tree traversal methods.

We'll cover the following...

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.

Implementation in C++

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

Yes, it is as simple as that!

C++
#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);
  }
}

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][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)O(n) because a total of nn 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.