im_priyank_jain Morris Traversal without using Recursion & Stack
Node pre; if(root == null) return; Node curr = root; while(curr != null){ if(curr.left == null){ System.out.print(curr.data+" "); curr = curr.right; }else{ pre = curr.left; while(pre.right !=null && pre.right != curr) pre = pre.right; if(pre.right == null){ pre.right = curr; System.out.print(curr.data+" "); curr = curr.left; }else{ pre.right=null; curr=curr.right; } } }
rshaghoulian O(1) space. Cool.
hammeramr Hey I'm not that sure either but this link says its O(n)
https://stackoverflow.com/questions/6478063/how-is-the-complexity-of-morris-traversal-on
rshaghoulian Hey there. My comment says it's O(1) space complexity. The time complexity is not O(1)
hammeramr Oh sorry, thanks for the clarification
alaniane Time complexity at worst case would be O(N2). You have at least one nested loop. However, the worst issue with this code is not the time or space complexity, but its cyclomatic complexity since that is what will create the greatest problem with maintaining the code.
ZeaLot4J It's the best solution.
grinev95 I still didn't understand how it works, but it looks cool :)
hammeramr [deleted]tigerleapgorge [deleted]cowarrior1 is the time complexity O(n^2) for this one?
Matt_Scandale Why are only C++ and Java allowed? How can others earn points?
wilsonpe66Asked to answer I am sorry I am not sure why. I am not a content creator for this site. I am just a user but I support your question. What is your language preference? I recommend contacting an admin on this. Of course, I can help with the algorithm, if you want.
zkarenAsked to answer Sorry I am not sure, too. I only tried C++ and Java.
pankaj_vir When python will be available to solve this problem?
AllisonP Python is now added and tested.
sungmkim80 Would you kindly add a C# to the template? And also how can I contact an admin to add templates to questions?
magoarcano I cannot use:
from __future__ import print_function
So I can print the nodes in the same line.
ayush571995 you can print by simply usint print 'data',
magoarcano No because print adds a new line at the end and I want to avoid that, so the test passes
ayush571995 See the comment use print data , It would do exactly
magoarcano Maybe I misunderstood, but if I do:
print 'data ' print 'data'
It will print:
data data
instead of:
data data
I need to print each output of the recursive function in the same line.
ayush571995 What I mean to say is use print "whatever you need to print" ,
Here last comma means it would not change the line after printing. For eg if I write
print 1, print 5 Output in Python 2.7 would be 1 5 and for the same thing in Python 3.0 you need to print it like
print(1,end=' ') print(5)
magoarcano Oh, I got it. Great! I didn't know it. Thank you very much!
mbilalbaqar In python 2 you can use a comma at the end of a print statement to supress newline.
def preOrder(root): if root: print root.data, if root.left: preOrder(root.left) if root.right: preOrder(root.right)
riwiem You can also use stdout.write from
systo suppress newlines:import sys # (...) sys.stdout.write(str(root.data) + ' ')
I've no idea why Python 3 is not available here.
end=''in a print function is so much more explicit and readable.
sureshmobiquick Do uwork in hckerrank
veervishu99 it is not showing python3 only showing python 2
PRASHANTB1984 This problem is fairly language agnostic. If you'd like to contribute templates in other languages do let us know.
pankaj_vir Ok, I will do.
jonmcclung What is a template? How does one make this and contribute it?
santhoshsekar95 you can also use 'c language' with compiler set as c++. the libraries will work
shanker4999 void preOrder(Node root) { if(root==null){ return ; } System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); }
muzic_maniac7 Can anyone please tell me what will be the complexity of this!
jsolanacasas I believe it is O(n) time complexity. Not sure for space complexity, O(log n)?
avmohan O(n) space complexity as well in the worst case - the tree is not necessarily balanced
m_edgaming91 Python 3 solution:
def preOrder(root): if root: print(str(root.data)+" ", end="") #print on same line preOrder(root.left) preOrder(root.right)
yannick_perrenet You could change the print statement to:
print(root.data, end=' ')
PkkdGuy You need not to do all that stuff to that print statement. CHEERS!!!
def preOrder(root): if root: print root.data, preOrder(root.left) preOrder(root.right)
yannick_perrenet I am sure this will not work in Python3, which is the version we are talking about.
PkkdGuy thats python 2 bro. yep its not working in python 3.
magoarcano It doesnt work in that way with python 2.
print root.data
prints with a new line at the end. You can import print function from future and use the 'end' parameter as Yannick commented
vshantam use
print( root.data ),
Insteed of
print root.data
holy_monk Here's one with recursion, makes life easier..!!
void preOrder(node *root) { printf("%d ", root->data); if(root->left) preOrder(root->left); if(root->right) preOrder(root->right); }
GencTasbasi You don't need ifs
gauravdhingra_g1 Wouldn't it raise an error, saying "None" object has not attribute "data"?
GencTasbasi It's basically like this:
void preOrder(Node root) { if(root == null) return; System.out.print(root.data); System.out.print(" "); preOrder(root.left); preOrder(root.right); }
gauravdhingra_g1 Yes, I think that would be good.
alaniane Adding the ifs prevents an extra push to the stack. Why push a null to the stack to check it and immediately return. So, although you could re-write the code:
void preOrder(node *root){ if(!root) return; printf("%d ", root->data); preOrder(root->left); preOrder(root->right); }
You have pushed two unnecessary items to the stack for every leaf in the tree and possibly one item to the stack for any branch that has only one child.
Mandar_Inamdar here is Python 2 solution:
def preOrder(root): if root: print(str(root.data)), #The comma at end prevents print from issuing a new line preOrder(root.left) preOrder(root.right)
melody_honkomp No Python3 available? And the Python2 seems not functioning correctly
thedurphy @PkkdGuy has the best Python2 solution I've seen. As for Python3, it should only differ slightly with the print function
Python 2
def preOrder(root): if root: print root.info, preOrder(root.left) preOrder(root.right)
Python 3 or Python 2 by importing
print_functionfrom__future__def preOrder(root): if root: print(root.info, end = ' ') preOrder(root.left) preOrder(root.right)
gauravdhingra_g1 How does
print root.info,work? I mean, if I use it in python2 myself I get an error.>>> r = "apple " >>> print r, File "<stdin>", line 1 print r, ^ SyntaxError: Missing parentheses in call to 'print' >>>
ventsi To eliminate the trailing space before or after the printed result I used the following:
void preOrder(Node root) { if(root == null) return; System.out.print(root.data); if(root.left != null){ System.out.print(" "); preOrder(root.left); } if(root.right != null){ System.out.print(" "); preOrder(root.right); } }
Note: it might not be required for passing the tests successfully, but just for fun.
merlina_escorcia can you write this code in Python 3?
dvcrn I have no idea about Java but it was fairly simple to traverse the tree without any knowledge of the language:
You always start left, then go right. Recurse deeper and print the value
void Preorder(Node root) { System.out.print(root.data + " "); if (root.left != null) { Preorder(root.left); } if (root.right != null) { Preorder(root.right); } }
PRASHANTB1984 Thank you for sharing your code!
sheelnidhi My code is same but I am getting error...
sheelnidhi Class Node { } I have uncommented this code.. Please suggest me.
mfinney can be done even more elegantly (less null checks)
void Preorder(Node root) {
if (root != null) { System.out.print(root.data + " "); Preorder(root.left); Preorder(root.right); }}
deucethecoder I also like this one because it deals with the case of having an empty tree.
Tolani This was in C++, but I'm sure you can translate it to java. If root is
NULLthen return means stop the recursionvoid preOrder(node *root) { if(root == NULL) return; cout << root->data << " "; preOrder(root->left); preOrder(root->right); }
arpitr You can't use return statement. The function's return type is void.
vidyasagarr7 This code doesnt pass the test cases.
bmpezzi I'm having an error that says that null isn't declared. I never had to do so. Does it require any include?
sandymark0346 im way late by now, but most likely you forgot to make "null" lowercase. in Java "NULL" doesnt work.
caroso1222 You would probably get an error because of the last space. It seems that they don't trim the console output before comparing.
artemshabliy [deleted]
ronaldalmeida How does this code work if root.left and root.right are both null, say for leaf nodes
sudan_sahab Here is what I did
int preOrder( struct node *root) { if(root==NULL) { return 0; } else { printf("%d ",root->data); preOrder(root->left); preOrder(root->right); } return 0; }
Sort 151 Discussions, By:
Please Login in order to post a comment