Clockwise Triangular Traversal of a Binary Tree

Approach

The best approach is to visit the nodes in clockwise order is to store them in a 2D array, ‘LEVEL’ based on their levels. For example, the tree's root would be on level zero and hence will be stored in an array as LEVEL[0]. When we move down in the tree level increases. For example, the immediate children of roots will be on level one.

Level in a Complete Binary tree will look something like this.

Once we have the level order 2D array of the tree, we can print layers in clockwise order. In every layer, we'll be printing the rightmost nodes moving from top to bottom, then printing the bottom-most array in the layer from right to left, and then printing the firstmost elements moving bottom to top.

Let’s see how the algorithm works.

1. Firstly calculate the height of the complete binary tree and store it into the ‘HEIGHT’ variable.
2. Next, create a 2D vector, ‘LEVELS’ of size ‘HEIGHT’.
3. Then populate the ‘LEVELS’ vector by using a recursive function findLevelOrder(). 
4. After that, visit the 2D vector layer by layer and do the following.
   1. Print the rightmost element moving down the row.
   2. Print the bottom-most row from right to left.
   3. Print the leftmost node moving up the row.

Now that we’ve understood the algorithm let’s try to code it.

Program

#include <iostream>
#include <vector>
using namespace std;

// Class for Linked List Node.
class Node
{
public:
   int data;
   
   // Pointer to the left node.
   Node *left;
   
   // Pointer to the right node.
   Node *right;
};

// Function to create a complete binary tree.
Node *createTree(int n, int pos)
{
   if (pos > n)
       return NULL;
       
   // Create a new node.
   Node *root = new Node();
   
   // Insert data into the root.
   root->data = pos;
   
   // Create Left and right subtree.
   root->left = createTree(n, pos * 2 + 1);
   root->right = createTree(n, pos * 2 + 2);
   
   // Return root.
   return root;
}

// Function that calculates the height of a complete binary tree.
int calculateHeight(Node *root)
{
   Node *temp = root;
   int count = 0;
   
   // Move left until you reach a ‘NULL’ pointer.
   while (temp != NULL)
   {
       count++;
       temp = temp->left;
   }
   
   // Return height.
   return count;
}

// Function to populate the level order vector for a tree.
void findLevelOrder(Node *root, int currLevel, vector<vector<int>> &levels)
{
   // If root is NULL then return.
   if (root == NULL)
       return;
       
   // Insert the node in its level.
   levels[currLevel].emplace_back(root->data);
   
   // Recurse of inserting the childrens.
   findLevelOrder(root->left, currLevel + 1, levels);
   findLevelOrder(root->right, currLevel + 1, levels);
}

// Function that prints out clockwise traversal of a tree.
void clockwiseTraversal(Node *root)
{
   // Calculate the height of the tree.
   int height = calculateHeight(root);
   
   vector<vector<int>> levels(height);
   
   // Populate the vector, ‘LEVELS’.
   findLevelOrder(root, 0, levels);
   
   // Printing the tree layer by layer.
   for (int i = 0; i < height; i++)
   {
       int j = height - i;
       
       // Firstly print all the right node moving down.
       for (int k = i; k < j; k++)
       {
           cout << levels[k][levels[k].size() - 1] << "  ";
           levels[k].pop_back();
       }
       
       // Next print the last row in reverse.
       for (int k = levels[j - 1].size() - 1; k >= i; k--)
       {
           cout << levels[j - 1][k] << "  ";
       }
       
       // Now print the leftmost nodes moving up.
       for (int k = j - 2; k > i + 1; k--)
       {
           cout << levels[k][0] << "  ";
       }
       
       // Now move to the next layer.
   }
}

int main()
{
   cout << "Enter the number of nodes in the tree: ";
   int n;
   cin >> n;
   
   Node *root = createTree(n, 0);
   
   cout << "ClockWise Triangular Traversal of a Binary tree is: ";
   clockwiseTraversal(root);
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the number of nodes in the tree: 16

Output

Clockwise Triangular Traversal of a Binary tree is: 0 2 6 14 16 15 7 3 1 5 13 12 11 10 9 8 4

Complexity Analysis

Time Complexity

O(N), where ‘N’ is the number of nodes in the Binary tree.

To build a level-order 2D array, we visit each node once. This takes O(N) time. And then, we traverse the 2D array once, taking O(N) time. Hence Time complexity is O(N+N) = O(N).

Space Complexity

The space complexity is O(N), where ‘N’ is the number of nodes in the binary tree.

Since we store all ‘N’ nodes in a 2D vector.

Frequently Asked Questions

What is meant by traversal?

Tree traversal is the process of visiting each node in a tree exactly once. If a search results in a visit to all the nodes, it is called a traversal.

What are recursive and non-recursive tree traversal?

Recursive traversals are easier to implement because you only have to worry about one node, and they use the stack to store the state for each call, making them faster.
However, non-recursive functions require you to store a list of all nodes for each level, and they can be far more complex than recursive ones.

What are the three common types of traversals?

In order

left-subtree --> visit the root --> right-subtree
Preorder

visit the root --> left-subtree --> right-subtree
Postorder

left-subtree --> right-subtree --> visit the root

For example:-        

• inorder: {5 , 15 , 18 , 20 , 25 , 30 , 35 , 40 , 45 , 50 , 60}
• preorder: {30 , 20 , 15 , 5 , 18 , 25 , 40 , 35 , 50 , 45 , 60}
• postorder: {5 , 18 , 15 , 25 , 20 , 35 , 45 , 60 , 50 , 40 , 30}
   

Conclusion

In the above blog, we saw how to traverse the complete binary tree in clockwise order. I hope you had fun reading this blog. Head over to Coding Ninjas Studio to read other such amazing blogs.

Coding NIjas has also released a new Mock Test Series for cracking top tech companies.

Recommended Reading:

• Binary Tree Postorder Traversal
• Burn Tree
• Specific Level Order Traversal of Binary Trees
• Level Order Traversal in Spiral Form

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 
   

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Thanks for reading.