Approach
We know the concept of level order traversal in a binary tree. So, here also, we will perform the breadth-first search.
Before moving on to the procedure of the level order traversal, we will introduce some terms for the nodes of the binary tree which we will use in this problem.
Layer - The layer contains nodes in a specific order. The nodes are considered from the bottom-left-most node next to the previous layer, and the layer ends with the upper-rightmost node next to the previous layer.
The root node of a layer - The root of a layer is defined as a node that is used to move downwards through the left children only.
Layer Head - It is defined as the first node in a layer of nodes of the binary tree.
The steps of the traversal are as follows:
-
Define a layer of nodes in a binary tree.
-
Declare a stack to store the nodes of each layer.
-
Next, define a queue to store the root of each layer.
-
Starting with the very first layer, we will push the root node of the first layer to the queue.
-
Declare an indicator say layerRoot, which is the node expected at the end of a layer with the current layer head.
-
In a while loop, perform the following steps until the queue is non-empty.
-
Obtain the root of the current layer from the front of the queue.
-
Check if the root is the layer head of a new layer. If so, then pop all the elements from the stack and print them. Note that the elements of the stack are the last layer elements.
-
Next, traverse the tree nodes from the upper right to the bottom left. For every node, check if it has the right child. Then, check if the current node is a layer head or not. If so, update the expected indicator to point to the layer head of the next layer.
-
Push the right child of the root to the queue.
-
Push the currently traversed node in that stack.
- In the end, when we have traversed all the layers, then the last layer might be still present in the stack. So, accordingly, pop the elements from the stack and print the layer.
Let’s see the code implementation and the time and space complexity analysis in the next section.
C++ Implementation
/*C++ code to print the Bottom-left to Upward-right
Traversal of the given Binary Tree*/
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
Node *newNode(int data)
{
Node *temp = new Node();
temp->data = data;
temp->right = NULL;
temp->left = NULL;
return temp;
}
// function to perform required traversal
vector<int> bottomLeftUpperRight(Node *root)
{
vector<int> traversal;// to store the data of nodes
stack<int> r; // to store all the nodes in a layer
queue<Node *> rootsQueue; // queue to store the root of every layer
rootsQueue.push(root);// pushing the layer head of the first layer
Node *layerRoot = root;// to store the layer head
// loop to traverse and print the layers
while (!rootsQueue.empty())
{
Node *front = rootsQueue.front(); // root of current layer
rootsQueue.pop();// pop the front of queue
if (layerRoot == front)
{
// the root layer is also the layer head
while (!r.empty())
{
traversal.push_back(r.top());
r.pop();
}
}
while (front)
{
if (front->right)
{
if (front == layerRoot)
{
layerRoot = front->right;
}
rootsQueue.push(front->right);
}
r.push(front->data);
front = front->left;
}
}
// insert all the elements remaining
while (!r.empty())
{
traversal.push_back(r.top());
r.pop();
}
return traversal; // Return the traversal of nodes
}
// function to construct binary tree from the character array
Node *buildBinaryTree(char *binaryTree)
{
Node *root = NULL;
queue<Node **> q;
int data = 0;
bool lastNull = false;
while (*binaryTree != '\0')
{
int d = *binaryTree - '0';
// if d is a digit then create a new node for it
if (d >= 0 && d <= 9)
{
data *= 10;
data += d;
lastNull = false;
}
// if d is N i.e. null
else if (*binaryTree == 'N')
{
data = 0;
q.pop();
lastNull = true;
}
else if (*binaryTree == ' ')
{
// check If last element is null or not
if (!lastNull)
{
// If root node is not NULL
if (root)
{
Node **p = q.front();
q.pop();
if (p != NULL)
{
*p = newNode(data);
q.push(&((*p)->left));
q.push(&((*p)->right));
}
}
else
{
root = newNode(data);
q.push(&(root->left));
q.push(&(root->right));
}
data = 0;
}
}
binaryTree++; // move to the next element
}
return root; // Return the root of the tree constructed
}
// function to print the result vector
void printVector(vector<int> &result)
{
for (int i = 0; i < result.size(); ++i)
{
cout << result[i] << " ";
}
cout << endl;
}
int main()
{
/*
the following character array represents the level order traversal of
the binary tree and N represents null
*/
char binaryTree[] = "1 2 3 4 5 N 6 N N 7 8 9 N";
Node *root = buildBinaryTree(binaryTree);
vector<int> result = bottomLeftUpperRight(root);
cout << "The required traversal of the binary tree is as follows: ";
printVector(result);
}
You can also try this code with Online C++ Compiler
Output
The required traversal of the binary tree is as follows: 4 2 1 7 5 3 8 9 6
Complexity Analysis
Time Complexity
O(n), where n is the number of nodes in the binary tree since we traverse all the nodes iteratively of the given binary tree, so the time complexity turns out to be O(n).
Space Complexity
O(n), as we use queue and stack as auxiliary space to complete the required traversal of the binary tree.
Check out Time and Space Complexity
Frequently Asked Questions
What is a binary tree?
It is a tree where every node has a maximum of two children. It cannot have more than two children. None of the nodes can have more than two children. That means it can be zero.
What is a root node?
The first node of a binary tree is called the root node.
List the major types of traversals in a binary tree.
Postorder traversal, Inorder traversal and Preorder traversal
Conclusion
In this article, we learned to solve the problem to traverse the given binary tree from the bottom left to the upward right.
We saw how we could use an existing algorithm to solve a new problem of the same type. Here, we used the well-known level order traversal to traverse the tree in the desired direction.
To learn binary trees from scratch, check out this amazing course - Learn Binary Trees.
Are you planning to ace the interviews with reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Recommended Reading:
Recommended problems -
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.
Cheers!
569+ registered 
