Tree left view input

#1

sir plzz help me with how to take level order input of a binary tree I am confused!

#2

Hello @khushi91200,

In Level Order, you insert the nodes/traverse the tree level wise.
i.e.
first node at level 0(Root)
then you start filling the next level i.e. level 1 from left to right
Similar order is followed for other nodes.

Let’s understand with the help of example given in the question:
1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1
-1 indicates no child.
The structure of the tree formed for the above example is:
_________________1
_________2______________3
_____4_______5_______________6

You can refer to the following code for better understanding:

Hope, this would help.
Give a like, if you are satisfied.

#3

can u plzz explain it i am unable to understand it

#4

Sure,

Note:
The code i have shared is a part of the entire program.
Thus you have to make a class node with data members:

  1. int data;
  2. node *left;
  3. node *right;
    I have added this class in the link i have shared earlier. You can check.

Now, coming back to your problem:
We are using a queue in order to form the tree level wise:
In a queue, elements are entered from rear(i.e. right) and removed from front(i.e. left)

Let’s understand with the help of an example:
1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1

first we are taking input d=1;
pushing it into the queue {1}
As we know that each node can have 2 children in a binary tree.
c1 and c2 are used for those children with c1 being left and c2 being a right child.

We will iterate the while loop till queue is not empty or we form the enitre tree.

  1. first iteration:
    f is a temporary variable of type node.
    it contains the element at the front(leftmost value) in the queue.
    so, f points to root i.e. node with value 1.
    pop the queue. Hence queue becomes: {} empty
    take next two inputs c1 and c2

    if(c1 is not -1) i.e. the left child of current node exists.
    make it f->left = c1=2
    push it into the queue: {2}

    if(c2 is not -1) i.e. the right child of current node exists.
    make it f->right =c2 =3
    push it into the queue: {2,3}

  2. Second iteration:
    so, f points to the node with value 2.
    pop the queue. Hence queue becomes: {3}
    take next two inputs c1 and c2

    if(c1 is not -1) i.e. the left child of current node exists.
    make it f->left = c1=4
    push it into the queue: {3,4}

    if(c2 is not -1) i.e. the right child of current node exists.
    make it f->right =c2 =5
    push it into the queue: {3,4,5}

  3. Third iteration:
    Now, f points to the node with value 3.
    pop the queue. Hence queue becomes: {4,5}
    take next two inputs c1 and c2

    if(c1 is not -1) i.e. the left child of current node exists.
    But, c1 is -1.
    So, this condition would not satisfy and f->left will keep pointing to NULL

    if(c2 is not -1) i.e. the right child of current node exists.
    make it f->right =c2 =6
    push it into the queue: {4,5,6}

  4. Fourth iteration:
    Now, f points to the node with value 4.
    pop the queue. Hence queue becomes: {5,6}
    take next two inputs c1 and c2

    if(c1 is not -1) i.e. the left child of current node exists.
    But, c1 is -1.
    So, this condition would not satisfy and f->left will keep pointing to NULL

    if(c2 is not -1) i.e. the right child of current node exists.
    But, c2 is -1.
    So, this condition would not satisfy and f->right will keep pointing to NULL

  5. Fifth iteration:
    Now, f points to the node with value 5.
    pop the queue. Hence queue becomes: {6}
    take next two inputs c1 and c2

    if(c1 is not -1) i.e. the left child of current node exists.
    But, c1 is -1.
    So, this condition would not satisfy and f->left will keep pointing to NULL

    if(c2 is not -1) i.e. the right child of current node exists.
    But, c2 is -1.
    So, this condition would not satisfy and f->right will keep pointing to NULL

  6. Sixth iteration:
    Now, f points to the node with value 6.
    pop the queue. Hence queue becomes: {6}
    take next two inputs c1 and c2

    if(c1 is not -1) i.e. the left child of current node exists.
    But, c1 is -1.
    So, this condition would not satisfy and f->left will keep pointing to NULL

    if(c2 is not -1) i.e. the right child of current node exists.
    But, c2 is -1.
    So, this condition would not satisfy and f->right will keep pointing to NULL

Now, the queue is empty.
Hence, the loop will terminate.

I hope you have understood the flow of the code that I have shared.
It is forming tree level by level i.e. stating from the root it fills each level one by one.

Hope, this would help.
Give a like, if you are satisfied.

1 Like
#5

thanks sir it helped me

#6

Anytime::wink:

Please, mark this doubt as resolved if you have no more questions regarding this doubt.

#7

thanks for such a wonderful explanation