1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
C++ Implementation
3.2.
Complexity Analysis
4.
4.1.
What is a binary tree?
4.2.
What is a root node?
4.3.
List the major types of traversals in a binary tree.
5.
Conclusion
Last Updated: Mar 27, 2024

# Bottom-left to upward-right Traversal in a Binary Tree

Yukti Kumari
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

In this article, we will see quite an interesting problem to traverse a binary tree from the bottom left to the upward right.

Letâ€™s get started with the problem statement.

## Problem Statement

You are given a Binary Tree, and the task is to print the Bottom-left to Upward-right Traversal of the given Binary Tree, i.e., the level order traversal having level as Bottom-left to Upward-right node.

Letâ€™ us understand through an example.

The required output is -

``4 2 1 7 5 3 8 9 6``

Explanation -

We have to perform level order traversal only, but the difference is that the level is from bottom-left to upward-right node.

The nodes of all the levels are as follows -

• Level 1 - 4  2  1
The path of the nodes goes from the bottom left to the upper right root node.

• Level 2 - 7 5 3

• Level 3  - 8 9 6

Please try to solve this problem on your own before moving on to further discussion here.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

``````

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

### 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!