Not getting correct output

#1


Not getting output , i have used created inorder array from preorder array and used both of them to create the bst but not getting output.

#2

hi @ujj1804_1156aee80205d0bf, check the updated code https://ide.codingblocks.com/s/659594

#3

Thank u sir but can u pls explain ?

n->left = create(pre, in_, ps+1, ps+idx-is, is, idx-1);
n->right = create(pre, in_, ps+1+idx-is, pe, idx+1, ie);

#4

@ujj1804_1156aee80205d0bf,
n->left = create(pre, in_, ps+1, ps+idx-is, is, idx-1);
this recursively calls to build the left child of the node
ps is preorder array’s starting index
is is inorder array’s starting index
idx is the pos of element found

int preorder the elements will be from ps+1 to ps+(idx-is)
in inorder the elements are from is to idx-1

similarly for n->right = create(pre, in_, ps+1+idx-is, pe, idx+1, ie);

#5

Sir thank u i have understood the code , but how did u make the logic for updating the ps,pe,is,ie everytime , is there any pattern or something ?

#6

@ujj1804_1156aee80205d0bf yes there is a pattern the numbers in the left of the found index in inorder array will be in left tree and after index till end will be in right tree

same for preorder there is a order

do a dry run yourself for a more better understanding…

#7

Sir i have done the dry run and was able to form the tree , just didnt understand how u thought updation of ps to ps+1+idx-is etc.

#8

@ujj1804_1156aee80205d0bf, these are the observation and previous learnings, I was able to came up with this

#10

Sir the doubt is clear just wanted to ask that i also did a similar thing in my code it showed segmentation fault why? I just did not use ps , pe ,is ,ie , I used start and end pointers.

#11

@ujj1804_1156aee80205d0bf, mabye somewhere it would have been reaching to NULL pointer so in trees and linkedlist u can always use more variables to make code little bit clear that will also help to avoid these errors :slight_smile:

#12

Oh but sir this code was given by sir in Binary tree section of the course in which we had to make binary tree from inorder and preorder of tree , so isn’t the way correct for BST also?

#13

@ujj1804_1156aee80205d0bf yeah that code is also correct
just write <=end instead of <end as you r passing n-1 from main function, both are correct and almost same…

1 Like
#14

Thank u sir got it ,doubt clear just a last question , so incase we have a right skewed tree the time complexity will be approx O(2 multiplied N) = O(N) as to left side of each node NULL will be attached and to the right of every node its child will be attached ?

#15

@ujj1804_1156aee80205d0bf its o(n^2) in worst case, as you are doing a linear seach to find element

1 Like
#16

Ok sir , incase we just talk about complexity of creating nodes and attaching to parent it’s will be O(N) and in total O(n square) due to linear search ? Thank u sir for replying to each of my doubt and clearing them.

#17

@ujj1804_1156aee80205d0bf yes

#18

Ok thank u sir… it’s clear