C++ Tutorial Index

C++ Tutorial C++ History C++ Installation C++ First Program C++ cin and cout C++ Data type C++ Variable C++ operator C++ Keywords

C++ Control Statements

C++ If C++ Nested if C++ If-else C++ If-else-if C++ Switch C++ Break C++ Continue C++ Goto C++ For loop C++ While loop C++ Do while loop

C++ Functions

C++ Call by Value C++ Call by Reference C++ Recursion Function C++ Inline function C++ Friend function

C++ Arrays

Single dimension array Two dimension array

C++ Strings

C++ Strings

C++ Inheritance

C++ Inheritance Single level Inheritance Multilevel Inheritance Multiple Inheritance Hierarchical Inheritance Hybrid Inheritance

C++ Polymorphism

C++ Polymorphism C++ Overloading C++ Overriding C++ Virtual Function

C++ Pointers

C++ Pointers C++ this pointer

C++ Exception Handling

C++ Exception Handling

C++ Constructors

C++ Constructors Default Constructor Parameterize Constructor Copy constructor Constructor Overloading Destructor

C++ File Handling

C++ File Handling C++ Writing to file C++ Reading file C++ Close file

Miscellaneous

C Vs C++ C++ Comments C++ Data Abstraction C++ Identifier C++ Memory Management C++ Storage Classes C++ Void Pointer C++ Array To Function C++ Expressions C++ Features C++ Interfaces C++ Encapsulation std::min in C++ External merge sort in C++ Remove duplicates from sorted array in C++ Precision of floating point numbers Using these functions floor(), ceil(), trunc(), round() and setprecision() in C++ C++ References C++ Friend Functions C++ Mutable keyword Unary Operators in C++ Initialize Array of objects with parameterized constructors in C++ Differences between #define & const in C/C++ C++ Program to Implement Shell Sort C++ Program to Implement Merge Sort Storage Classes in C Vector resize() in C++ Passing by Reference Vs. Passing by the pointer in C++ Free vs delete() in C++ goto statement in C and C++ C++ program to read string using cin.getline() C++ String Concatenation Heap Sort in C++ Swap numbers in C++ Input Iterators in C++ Fibonacci Series in C++ C ++ Program: Alphabet Triangle and Number Triangle C++ Program: Matrix Multiplication C++ Program to Print Fibonacci Triangle Stack in C++ Maps in C++ Queue in C++ C++ Bitset C++ Algorithms Priority Queue in C++ C++ Multimap C++ Deque Function Pointer in C++ Sizeof() Operators in C++ C++ array of Pointers free() Vs delete in C Timsort Implementation Using C++ CPP Templates C++ Aggregation C++ Enumeration C++ Math Functions C++ Object Class C++ Queue Initialize Vector in C++ Vector in C++ C++ STL Components Function overloading in C++ C++ Maximum Index Problem C++ find missing in the second array C++ Program to find the product array puzzle C++ Program To Find Largest Subarray With 0 Sum C++ Program To Move All Zeros To The End Of The Array C++ Program to find the element that occurs once C++ Program to find the largest number formed from an array Constructor Vs Destructor C++ Namespaces C++ OOPs Concept C++ Static C++ Structs C++ Try-Catch C++ User Defined Exceptions C++ Virtual Destructor C++ vs C# Malloc() and new in C++ Palindrome Number Program in C++ Snake Code in C++ Splitting a string in C++ Structure Vs Class in C++ Virtual Function Vs Pure Virtual Function C++ Bidirectional Iterators C++ Forward Iterators C++ Iterators C++ Output Iterators C++ Range-based For Loop Converting string into integer in C++ LCM Program in C++ Type conversion in C++ Add two numbers using the function in C++ Advantage and disadvantage friend function C++ Armstrong Number Program in C++ ATM machine program in C++ using functions Binary to Decimal in C++ Bit Manipulation in C++ C++ Constructor C++ Dijkstra Algorithm Using the Priority Queue C++ int into String C++ Signal Handling Decimal to Binary in C++ Decimal to Hexadecimal in C++ Decimal to Octal in C++ Factorial Program in C++ Function in C++ Hexadecimal to Decimal in C++ Octal to Decimal in C++ Reverse a Number in C++ Structure Vs Class in C++ C++ Forward Iterators C++ Output Iterators C++ Prime number program Char Array to String in C++ Constructor Overloading in C++ Default arguments in C++ Different Ways to Compare Strings in C++ Dynamic Binding in C++ Program to convert infix to postfix expression in C++ SET Data Structure in C++ Upcasting and Downcasting in C++ Reverse an Array in C++ Fast Input and Output in C++ Delete Operator in C++ Copy elision in C++ C++ Date and Time C++ Bitwise XOR Operator Array of sets in C++ Binary Operator Overloading in C++ Binary Search in C++ Implementing the sets without C++ STL containers Scope Resolution Operator in C++ Smart pointers in C++ Types of polymorphism in C++ Exception Handling in C++ vs Java Const Keyword in C++ Type Casting in C++ Static keyword in C++ vs Java Inheritance in C++ vs Java How to concatenate two strings in C++ Programs to Print Pyramid Patterns in C++ swap() function in C++ Structure of C++ Program Stringstream in C++ and its applications rand() and srand() in C / C++ C++ Ternary Operator C++ Scope of Variables While Loop Examples in C++ Star pattern in C++ using For Loops For Loop Examples in C++ Do-While Loop Examples in C++ Top 5 IDEs for C++ That You Should Try Once Assertions in C/C++ C++ Convert Int to String Continue in C++ While loop Diamond Pattern in C++ using For Loop How to Reverse a String in C++ using Do-While Loop How to Reverse a String in C++ using For Loop How to Reverse a String in C++ using While Loop Infinite loop in C++ Loops in C++ Returning Multiple Values from a Function using Tuple and Pair in C++ wcscpy(), wcslen(), wcscmp() Functions in C++ Auto keyword in C++ C++ 11 vs C++ 14 vs C++ 17 C++ STL (Standard Template Library) Differences Between C Structures and C++ Structures Divide by Zero Exception in C++ Dynamic Constructor in C++ Dynamic Memory Allocation in C++ Find the Size of Array in C/C++ without using sizeof() function Floating Point Operations and Associativity in C, C++ and Java Hello World Program in C++ How to create a table in C++ How to Setup Environment for C++ Programming on Mac Implementation of a Falling Matrix in C++ Message Passing in C++ Pointer to Object in C++ Templates in C++ vs Generics in Java Ways to Copy a Vector in C++ What does Buffer Flush mean in C++ sort() function in C++ Structure Sorting (By Multiple Rules) in C++ Similarities between C++ and Java std::distance in C++ Array program in C++ C++ Tricks for Competitive Programming Desired Capabilities in Selenium Web Driver in C++ Socket Programming in C++ Template Specialization in C++ Classes and Objects in C++ Convex hull Algorithm in C++ DES in C++ C++ vardiac() function Difference between Two Sets in C++ Difference between Exit and Return Structured Binding in C++ Differences between Local and Global Variable Bitwise Operator vs Logical Operator Difference between OOP and POP in C++ Fork in C++ Functors in C++ How to call a void function in C++ How to create a directory or folder in C/C++ How to create a library in C++ How to create a stack in C++ How to create the Processes with Fork in C++ How to Handle Divide by Zero Exception in C++ Lambda Expression in C++ Pattern programs in C++ Roadmap to C++ Programming Substring in C++ Virtual base class in C++ Bits stdc++.h in C++ Top 14 Best Free C++ IDE (Editor & Compiler) for Windows in 2022 Bitmasking in C++ Auto Keyword in C++ Features of OOPS in C++ Hospital Management Project in C++ How to Declare Unordered Sets in C++ How to Sort an Array in C++ Include Guards in C++ Iostream in C++ Method overriding in C++ How to run program in turbo c++ How to Use Getline in C++ Leap Year Program in C++ Naming Convention in C++ New Operator in C++ Nullptr in C++ Object Slicing in C++ Principles of Object-Oriented Programming in C++ Processing strings using std string stream in C++ Pure Virtual Function in C++ With Example Program Random Number Generator in C++ Singleton Design Pattern in C++ Size_t Data Type in C++ Skyline Problem in C++ System() function in C++ Web Development in C++ Data Hiding in C++ Difference between exit() and _Exit() in C++ Hashing in C++ Object in C++ Sum of all Elements between k1’th and k2’th Smallest Elements Virtual class in C++ Vector Size in C++ Top best IDEs for C/C++ Developers in 2022 Tensorflow in C++ Sliding Window Technique in C++ Reverse String Word-Wise in C++ Returning a Function Pointer from a Function in C/C++ RTTI in C++ Pthreads or POSIX Threads in C++ Reserved Keywords in C++ Passing a Vector to a function in C++ 10 Best C and C++ Books for Beginners & Advanced Programmers Add two numbers represented by two arrays in C++ Array of Object in C++ C++ Program For FCFS Containership in C++ Counting Frequencies of Array Elements in C++ Decltype type Specifier in C++ Dynamic _Cast in C++ Difference between int main() and int main(void) in C/C++ Depth First Search Program to Traverse a Graph in C++ Features and Use Of Pointers in C/C++ Fread Function in C++ Programming Fscanf Function in The C++ Functions in C++ With Types and Examples Gmtime Function in C/C++ How is Multiset Implemented in C++ How to Build a Program in C++ How to Declare a 2d Array Dynamically in C++ inheritance Program in C++ int Max and int Min in C/C++ is It Fine to Write Void Main Or Main in C/C++ How to create a button in C++ abs() function in C++ Compile Time Polymorphism in C++ Division in C++ Factorial of a Number in C++ using while Loop Multiset in C++ 4 Pillars of OOPs Approach in C++ Backtracking Time Complexity in C++ C++ Global Variable C++ Pipe Tutorial Observer Design Pattern in C++ Private Inheritance in C++ Pthread in C++ Parameters SDL library in C++ with Examples Pointers in C++ Abstract Factory Design Pattern in C++ Ascending order in C++ How the value is passed in C++ Call by Pointer in C++ Constexpr in C++ Deadlock in C++ Design Patterns in C++ Factory Method for Designing Pattern in C++ How to calculate size of string in C++ Name Mangling and extern in C++ Preventing Object Copy in C++ Program that produces different results in C and C++ Quick Sort in C++ Single Handling in C++ Type difference of Character literals in C VS C++ Use of Inheritance in C++ User-defined literals in C++ Vector methods in C++ Void * in C and C++ Zombie and Orphan Process in C++ Isprint() in C++ List and Vector in C++ List iterators in C++ Merging Two Vectors in C++ Sleep function in C++ Stoi function in C++ String erase() in C++ String Trim in C++ When should we write own Assignment operator in C++ C++ tcp client server example C++ tcp server example Early Binding and Late Binding in C++ Factory Design Pattern in C++ Fisher-Yates shuffle algorithm in C++ For Auto in C++ Group anagrams in C++ How to convert binary string to int in C++ How to convert string to float in C++ How to remove space from string in C++ How to use pair in C++ How to use the string find() in C++ Dynamic Casting in C++ 2D Vector Initialization in C++ C++ GUI Visual Studio C++ IPC C++ Macro Function Example C++ Permutation Overloading Stream Insertion in C++ Overloading array Index operator in C++ Operators that cannot be overloaded in C++ Operator overloading in C++ isprint() function in c++ Is_trivial function in C++ Is assignment operator Inherited in C++ div() function in C++ Default Assignment Operator and References in C++ Copy Constructor vs Assignment Operator in C++ Conversion Operator in C++ Array sum in C++ STL C++ Define Macro C++ Design C++ Factory Pattern TCP Client Server Example in C++ Convert String to Uppercase in C++ exit() and _Exit() in C and C++ Initializer list in C++ Iterator invalidation in C++ Lower bound in C++ Modulus of Two float numbers or double number Pass by value in C++ Set insert function in C++ Std partition_point in C++ Unary Operator Overloading in C++ Using Default Arguments with Virtual Functions Virtual Functions and Runtime Polymorphism What is endl in C++ What is Unary Operator Overloading in C++ Which operators cannot be overloaded in C++ C++ Program to Divide the String Into N equal Parts Gray Code to Binary Code in C++ How to get the value of pi in C++ Multimap value_comp() function in C++ Vector of Vectors in C++ Naïve Bayes Algorithm in C++ Minimum Cost Path Problem in C++ 10 C++ Programming Tricks You Should Know btowc() function in C++ forward_list::cend() in C++ Unordered_multimap max_load_factor() function in C++ Cpp_int in c++ Dynamic Objects in C++ FLOCK() FUNCTION IN C++ Generate Random Double Numbers in C++ How to Assign Infinity to a Number in C++ Jump statements in C++ Multipath inheritance in C++ Out of Range Exception in C++ Size of Class in C++ Size of string in C++ std::binary_negate in c++ Thread_local in C++ Tokenizing a String in C++ Ancestors of a Node in Binary Search Tree C++ program for Double to String Conversion C++ Program to Demonstrate Use of Formatting Flags on Float Output Clamp in C++ K-Dimensional Tree in C++ Mutable Lambda in C++ Power Set in C++ Program to Find Sum of Geometric Progression Std::Back_inserter in C++ Strpbrk() function in C++ Size of int in C++ TYPES OF MANIPULATORS IN C++ Double colon in C++ How to sort vector in C++ How to use Setprecision in C++ How to write a Vector in C++ Insertion in Splay Tree in C++ Merge Sort Algorithm in C++ Printing a Character using ASCII value in C++ Regex in C++ Size of Data Types in C++ Sqrtf() function in C++ Static Casting in C++ Using Range in Switch Case in C++ wcstoimax() and wcstoumax() function in C++ What is float in C++ What is the Diamond Problem in C++ Best way to learn C++ ios setstate() function in C++ Nested Namespace in C++ Single Inheritance in C++ std::fixed, std::scientific, std::hexfloat, std::defaultfloat in C++ StringStream in C++ for Decimal to Hexadecimal and back The OFFSETOF() macro in C++ Difference between std::next and std::advance in C++ Hiding of all overloaded methods with same name in base class in C++ C++ program to concatenate two strings using operator overloading Difference between array::fill() and array::swap() in C++ Difference between Friend Function and Virtual Function in C++ Semaphores in C++ Seekg in C++ UDP server- client implementattion in C++ What is long long in C++ CSV file management using C++ Toggle bits of a number except first and last bits in C++ Trailing Return Type C++ 11 Binary search implementation in C++ Different Versions of C++ What is Cascading in C++ Background Colour in C++ BOOL DATATYPE IN C++ BIT VECTORS IN C++ Literals in C++ Application of pointer in C++ Index with minimum sum of prefix and suffix sums in an array in C++ Maximum sum Bi-tonic sub-sequence in C++ std::optional in C++ C/C++ program for triangular matchstick number COUT COMMAND IN C++ LANGUAGE Adjacency matrix program in C++ language Difference between Null String and Empty String in C++ Character data type in c++ Constructors in Inheritance C++ Comma Operator Overloading in C++ Structure and Class in C++ Template Definition in C++ Tree Data Structure in C++ Typename in C++ C++ program to implement the bin packing algorithm How to merge multiple std::sets into a single std::set in C++? Stack Clear C++ C++ Friend Class Seekg in C++ Semaphores in C++ C++ Exceptions Difference Between C and C++ Double-linked list program in C++ Color Code in C++ CRC Program in C++ Anti-Clockwise spiral traversal of a binary tree in C++ Advantages of OOP in C++ Cryptarithmetic Puzzle in C++ Angular sweep algorithm in C++

Anti-Clockwise spiral traversal of a binary tree in C++

In this article, you will learn about the anti-clockwise spiral traversal of a binary tree in C++ with its algorithm and example.

Introduction:

Within the field of tree traversals, the anti-clockwise spiral traversal offers a visually appealing and thought-provoking look at the architecture of a binary tree. It winds its way around the tree in a mesmerizing dance, defying convention by going against the usual left-to-right or right-to-left directions and visiting nodes in a distinctive spiralling pattern.

Algorithm:

Initialize variables:

  • i: Starts at 1, which represents the level to begin from (bottom level for anti-clockwise spiral).
  • j: Starts at the height of the tree, which represents the level to end at (root level).
  • flag: Boolean variable, which is initially set to false to indicate right-to-left traversal.

Loop until all levels are covered:

  • Check the flag value:
  • flag is true (left-to-right):
  • Traverse levels from i (current bottom level) to j (current top level), printing node data at each level.
  • flag is false (right-to-left):
  • Traverse levels from j (current top level) down to i (current bottom level), printing node data at each level.
  • Change the flag value to its opposite for the next level.
  • Update i and j according to the flag value:
  • flag is true (left-to-right):Increment i to move down to the next level.
  • Decrement j to exclude the top level for left-to-right traversal.
  • flag is false (right-to-left):
  • Increment i to move down to the next level for right-to-left traversal.

Data Structures:

No stacks or queues are explicitly required for this algorithm.

Auxiliary variables:

i, j: These variable track the current and ending levels for traversal.

flag: It indicates the direction of traversal (left-to-right or right-to-left).

Implementation:

The provided C++ code implements the algorithm with these improvements:

  • Error handling: It checks for empty trees and invalid level values.
  • printNode function: It replaces with your specific logic to print node data at a given level (might involve level order traversal for larger trees).

Example:

Let us take an example to illustrate the anti-clockwise spiral traversal of a binary tree in C++.

#include 

#include 

#include 

using namespace std;

struct TreeNode {

    int value;

    TreeNode* left;

    TreeNode* right;

    TreeNode(int value) : value(value), left(nullptr), right(nullptr) {}

};

int calculateHeight(TreeNode* root);

void printSpiralLevel(TreeNode* root, int level, bool leftToRight);

void spiralTraversal(TreeNode* root) {

    if (!root) {

        return;

    }

    int treeHeight = calculateHeight(root);

    bool leftToRight = false;

    for (int currentLevel = 1; currentLevel <= treeHeight; currentLevel++) {

        printSpiralLevel(root, currentLevel, leftToRight);

        leftToRight = !leftToRight;

    }

}

int calculateHeight(TreeNode* root) {

    if (!root) {

        return 0;

    }

    int leftHeight = calculateHeight(root->left);

    int rightHeight = calculateHeight(root->right);

    return max(leftHeight, rightHeight) + 1;

}

void printSpiralLevel(TreeNode* root, int level, bool leftToRight) {

    if (!root) {

        return;

   }

    if (level == 1) {

        cout << root->value << " ";

    } else if (level > 1) {

        if (leftToRight) {

            printSpiralLevel(root->left, level - 1, leftToRight);

            printSpiralLevel(root->right, level - 1, leftToRight);

        } else {

            printSpiralLevel(root->right, level - 1, leftToRight);

            printSpiralLevel(root->left, level - 1, leftToRight);

        }

    }

}

TreeNode* constructTree() {

    int rootValue;

    cout << "Enter value for root node: ";

    cin >> rootValue;

    TreeNode* root = new TreeNode(rootValue);

    queue nodesQueue;

    nodesQueue.push(root);

    while (!nodesQueue.empty()) {

        TreeNode* currentNode = nodesQueue.front();

        nodesQueue.pop();

        int leftValue, rightValue;

        cout << "Enter left child value of " << currentNode->value << " (or -1 if none): ";

        cin >> leftValue;

        if (leftValue != -1) {

            currentNode->left = new TreeNode(leftValue);

            nodesQueue.push(currentNode->left);

        }

        cout << "Enter right child value of " << currentNode->value << " (or -1 if none): ";

        cin >> rightValue;

        if (rightValue != -1) {

            currentNode->right = new TreeNode(rightValue);

            nodesQueue.push(currentNode->right);

        }

    }

    return root;

}

int main() {

    TreeNode* root = constructTree();

    spiralTraversal(root);

    return 0;

}

Output:

Explanation of the code:

  • In this example, the antiClockwiseSpiralTraversal function takes the root node of the binary tree as input.
  • After that, the height function calculates the height of the tree efficiently.
  • Next, the printNode function is a placeholder that replace it with your actual printing logic, depending on your requirements.
  • The main loop iterates until all levels (i <= j) are covered.
  • Inside the loop, the flag value determines the direction of traversal.
  • Levels are traversed, and nodes are printed according to the direction and current level.
  • The flag and level indicators are updated for the next iteration.

Time Complexity Analysis:

Constructing the Tree:

  • The amount of nodes in the tree determines how time-consuming it is to build.
  • The user enters the left and right child values of each node, yielding a linear time complexity of O(N), where N is the total number of nodes.

Calculating Tree Height:

  • The calculateHeight function iteratively goes through the whole tree to determine the height of a tree.
  • The temporal complexity is O(N), where N is the number of nodes because each node is visited once.

Spiral Traversal:

  • The spiral traversal function goes through the tree's levels one by one until it reaches its peak.
  • The printSpiralLevel function is executed for each level, traversing the level's nodes.
  • In the worst-case scenario, when all nodes are visited once, the time complexity is O(N), where N is the total number of nodes.
  • Overall, the time complexity of the code is O(N), where N is the number of nodes in the tree.

Space Complexity Analysis:

Tree Construction:

  • The queue to build trees and the tree nodes must be stored somewhere.
  • This section has an O(N) space complexity, where N is the number of nodes in the tree.

Calculating Tree Height:

  • The tree height affects the space complexity of the recursive calls to calculateHeight.
  • The space complexity is O(H), where H is the tree's height in the worst scenario when the tree is skewed.

Spiral Traversal:

  • The tree's height also affects the space complexity during the spiral traversal.
  • The space complexity is O(H) in the worst scenario, where the tree is skewed.

← Prev