Bottom view of a Binary Tree

The bottom view of a binary tree is the number of nodes visible when viewed from the bottom. At every horizontal distance, there would be exactly one node that will appear in the bottom view. The horizontal distance is measured with the root serving as a reference; then, we measure each node’s left and right deviations.

Here, the nodes four, eight, six, nine, and seven are viewed from the bottom hence they will come in the bottom view of a tree.

Approach

  1. Do a level order traversal of the tree.
  2. Assign horizontal distance to each node of Binary Tree and replace the same horizontal distance node in a map with key as the distance to obtain the Bottom View.
  3. Make key as distance and data as value for the map.
  4. Perform it for every node in the tree.

C++ code:

    Input:

    8

    1 2 L

    1 3 R

    2 4 L

    2 5 R

    3 6 L

    3 7 R

    5 8 L

    6 9 R

Visualization of the tree

            1

         /     \

        2       3

      /   \    /   \

    4     5 6     7

          /    \

        /       \

       8        9

Output:

Bottom View of Binary Tree:

4 8 6 9 7

Pin It on Pinterest

Share This