Bottom-left to upward-right Traversal in a Binary Tree
Introduction
In this article, we will see a quite 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’ 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.
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-right most 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 a 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 6Time 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.
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
Key Takeaways
In this article, we learnt 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 of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!
Previous Article 
Comments
No comments yet
Be the first to share what you think