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

Yukti Kumari
Last Updated: May 13, 2022

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 6

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.

 

Frequently Asked Questions

  1. 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.
     
  2. What is a root node?
    The first node of a binary tree is called the root node.
     
  3. 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!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think