Posted on by Kalkicode
Code Binary Tree

Print Bottom-Left View of a Binary Tree

In this article, we will tackle the problem of printing the bottom-left view of a binary tree. This problem requires us to find and print the leftmost elements at each level of the binary tree when viewed from the bottom. To solve this problem, we will use a depth-first search (DFS) approach to traverse the tree and keep track of the leftmost elements at each level.

Bottom Left View of a Binary Tree

Problem Statement

Given a binary tree, we want to print the bottom-left view of the tree. The bottom-left view of a binary tree is the set of nodes visible when the tree is viewed from the left side at each level. In other words, for each level of the tree, we want to print the leftmost node at that level.

Example

Let's consider a binary tree as an example:


     10
    /  \
   2    4
  /    / \
 3    6   5
       \
        7
      /  \
     8    11

The bottom-left view of this tree is [3, 6, 8, 11] when viewed from the left side at each level, as indicated by the arrows in the tree diagram.

Idea to Solve the Problem

To print the bottom-left view of the binary tree, we can perform a depth-first traversal of the tree while maintaining a record of the leftmost node at each level. We will use an unordered map to store this information, where the key will represent the level of the node, and the value will be the leftmost node's value at that level. We'll start the traversal from the root node with a distance of 0 and increment the distance as we move to the right child and stay at the same distance when moving to the left child.

Pseudocode

Here is the pseudocode for solving the problem:

function bottomLeftView(node, distance, record):
        if node is not null:
            record[distance] = node.data
            bottomLeftView(node.right, distance + 1, record)
            bottomLeftView(node.left, distance, record)
    
    function printBottomLeft():
        record = empty unordered map
        bottomLeftView(root, 0, record)
        distance = 0
        while distance < size of record:
            print record[distance]
            increment distance by 1

Algorithm Explanation

  1. We start by initializing an empty unordered map called record to store the leftmost nodes at each level.
  2. We call the bottomLeftView function starting from the root node with an initial distance of 0.
  3. In the bottomLeftView function:
    • If the current node is not null, we update the record with the node's data at the current distance.
    • Then, we recursively call the function for the right child with an increased distance (moving right).
    • We also recursively call the function for the left child without changing the distance (moving left).
  4. After the traversal is complete, we iterate through the record map, starting from distance 0 and printing the leftmost node's value at each level.
  5. We increment the distance by 1 in each iteration until we have printed all the leftmost nodes at each level.

Code Solution

Time Complexity of the Code

The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the depth-first traversal, and the map operations take constant time.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment