Why this code does not pass testcase 1?

#1
#2

your approach is not correct
for the input
20 8 22 5 3 4 25 -1 -1 10 14 -1 -1 -1 -1 -1 -1 -1 -1
Your Output
20 8 5 10
Correct Output
5 10 4 14 25

Detailed algorithm

Given a Binary Tree, we need to print the bottom view from left to right. A node x is there in output if x is the bottommost node at its horizontal distance.

Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

Examples:

                  20
                /    \
              8       22
            /   \      \
          5      3      25
                / \      
              10    14

For the above tree the output should be 5, 10, 3, 14, 25.

If there are multiple bottom-most nodes for a horizontal distance from root, then print the later one in level traversal. For example, in the below diagram, 3 and 4 are both the bottom-most nodes at horizontal distance 0, we need to print 4.

                  20
                /    \
              8       22
            /   \    /   \
          5      3 4     25
                / \      
              10    14

For the above tree the output should be 5, 10, 4, 14, 25.

Approach

The following are steps to print Bottom View of Binary Tree.

  1. We put tree nodes in a queue for the level order traversal.
  2. Start with the horizontal distance(hd) 0 of the root node, keep on adding left child to queue along with the horizontal distance as hd-1 and right child as hd+1.
  3. Also, use a TreeMap which stores key value pair sorted on key.
  4. Every time, we encounter a new horizontal distance or an existing horizontal distance put the node data for the horizontal distance as key. For the first time it will add to the map, next time it will replace the value. This will make sure that the bottom most element for that horizontal distance is present in the map and if you see the tree from beneath that you will see that element.

you can take help from reference Code

Reference Code

#3

the output you are showing is bottom view of the tree we have to output left view in the given ques

#4

sorry i think you are asking about bottom view

in your code build tree function is completely incorrect
for input
1 2 3 -1 4 -1 -1 -1 5 -1 6 -1 -1
preorder of your code is 1 2 3 4
which is wrong

correct way of building tree

node* BuildTree() {
    int d;
    cin >> d;
    if (d == -1)return NULL;
    node* root = new node(d);
    queue<node*>q;
    q.push(root);
    while (!q.empty()) {
        node* temp = q.front();
        q.pop();
        int lc, rc;
        cin >> lc >> rc;
        if (lc != -1) {
            temp->left = new node(lc);
            q.push(temp->left);
        }
        if (rc != -1) {
            temp->right = new node(rc);
            q.push(temp->right);
        }
    }
    return root;
}
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.