Given a Complete Binary Tree, the task is to print the elements in the Clockwise Triangular traversal order.
Examples :
Input :
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /\
8 9 10 11
Output : 1, 3, 7, 11, 10, 9, 8, 4, 2, 6, 5
Approach :
Create a vector tree[] where tree[i] will store all the nodes of the tree at level i. Take an integerk which keeps track which level we are traversing other integer and cycle which keep tracks how many cycles has been completed. Now, start printing the nodes the rightmost remaining node whiach has not been traversed yet & keep moving down until you reach down to the last level which has not been traversed now print this level from right to left, then move print leftmost remaining leftmost element of each level starting from last level to moving to the uppermost level whose elements has all not been traversed yet, now again do the same thing until all elements has not been traversed.
Implementation :
// C++ program to print Clockwise
// Triangular traversal of complete binary
// tree
#include <bits/stdc++.h>
using namespace std;
<figure class="wp-block-image size-large" data-w3c-figure="post-62211-1.png"><img width="665" height="371" src="https://w3colleges.org/wp-content/uploads/2026/11/post-62211-1-1024x572.png" class="attachment-large size-large" alt="A complete binary tree with 11 nodes and numbered arrows tracing the clockwise path 1 3 7 11 10 9 8 4 2 6 5." loading="lazy" decoding="async" srcset="https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?resize=1024%2C572&ssl=1 1024w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?resize=300%2C168&ssl=1 300w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?resize=768%2C429&ssl=1 768w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?resize=1536%2C858&ssl=1 1536w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?resize=2048%2C1143&ssl=1 2048w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?resize=665%2C371&ssl=1 665w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?w=1330&ssl=1 1330w, https://i0.wp.com/w3colleges.org/wp-content/uploads/2026/11/post-62211-1.png?w=1995&ssl=1 1995w" sizes="auto, (max-width: 665px) 100vw, 665px" /></figure>
const int sz = 1e5;
int maxLevel = 0;
// Adjacency list representation
// of the tree
vector<int> tree[sz + 1];
// Boolean array to mark all the
// vertices which are visited
bool vis[sz + 1];
// Integer array to store the level
// of each node
int level[sz + 1];
// Array of vector where ith index
// stores all the nodes at level i
vector<int> nodes[sz + 1];
// Utility function to create an
// edge between two vertices
void addEdge(int a, int b)
{
// Add a to b's list
tree[a].push_back(b);
// Add b to a's list
tree[b].push_back(a);
}
// Modified Breadth-First Function
void bfs(int node)
{
// Create a queue of {child, parent}
queue<pair<int, int> > qu;
// Push root node in the front of
// the queue and mark as visited
qu.push({ node, 0 });
nodes[0].push_back(node);
vis[node] = true;
level[1] = 0;
while (!qu.empty()) {
pair<int, int> p = qu.front();
// Dequeue a vertex from queue
qu.pop();
vis[p.first] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
for (int child : tree[p.first]) {
if (!vis[child]) {
qu.push({ child, p.first });
level[child] = level[p.first] + 1;
maxLevel = max(maxLevel, level[child]);
nodes[level[child]].push_back(child);
}
}
}
}
// Utility Function to display the pattern
void display()
{
// k represents the level no.
// cycle represents how many
// cycles has been completed
int k=0,cycle=0;
// While there are nodes left to traverse
while(cycle-1<=maxLevel/2){
// Traversing rightmost element
// in each cycle as we move down
while (k<maxLevel-cycle){
int j = nodes[k].size()-1;
cout << nodes[k][j-cycle] << " ";
k++;
}
// Traversing each element of remaing
// last level from right to left
if(k==maxLevel-cycle)
{
int j = nodes[k].size()-1;
for(j-=cycle;j>=cycle;j--)
cout << nodes[k][j] << " ";
}
k--;
// Traversing leftmost remaing element
// in each cycle as we move up
while(k>cycle)
{
cout << nodes[k][cycle] << " ";
k--;
}
// No of cycles completed
cycle++;
// updating from which level to
// start new cycle
k = cycle + 1;
}
}
// Driver code
int main()
{
// Number of vertices
int n = 31;
// Initialisng a full complete
// binary tree of height 5
for(int i=1;i<=12;i++){
// adding edge to a binary tree
addEdge(i, 2*i);
addEdge(i, 2*i+1);
}
// Calling modified bfs function
bfs(1);
display();
return 0;
}
Output : 1 3 7 15 25 24 23 22 21 20 19 18 17 16 8 4 2 6 14 13 12 11 10 9 5 1 3 7 15 25 24 23 22 21 20 19 18 17 16 8 4 2 6 14 13 12 11 10 9 5
Time Complexity : O(n)
