Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
C++ Implementation
3.2.
Complexity Analysis
4.
Frequently Asked Questions
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

Author 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.

Tree

 

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

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!

Previous article
Morris Traversal Postorder
Next article
Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree
Live masterclass