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; } } }
RodneyShag 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
RodneyShag 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.
cellepo I don't think so, because each node is travelled through at most 3 times (see https://stackoverflow.com/a/53608069/1357094). And accordingly, O(3n) = O(n) when analyzing time complexity (3n & n are both equivalent "linear" complexity).
lanianeals [deleted]nebasuke Thanks for providing that link. See also https://cs.stackexchange.com/questions/16833/can-a-tree-be-traversed-without-recursion-stack-or-queue-and-just-a-handful-o
Personally, I enjoyed reading part of the "Morris's Tree Traversal Algorithm Reconsidered" paper.
ZeaLot4J It's the best solution.
tordjarv No it is not, this would be a terrible solution if it is part of a multithreaded program other threads might use the tree at same time and assume incorrectly that the tree actually is a tree (since the code introduces cycles). It would also be a terrible solution if you did something more complicated with each node value than just printing them, since if an exception is thrown the tree may no longer be a tree (since it might have one cycle). While recursive solutions has their own problems (such as heavy use of the call stack) theses problems are local and easier to maintain. Other non-recursive solutions where you introduce temporary data structures (such as stacks) are preferable unless you are running on a system with very strict memory restrictions, but in those cases you would not use Java anyway.
cellepo With respect to context of this problem as this HackerRank question, @ZeaLot4J is correct because this has the most efficient complexities (both time and space). While @tordjarv comments about other scenarios (like multi-threading) make some sense, they are contexts different from this HackerRank question.
Rexxx I still didn't understand how it works, but it looks cool :)
sandeshthakre619 XD XD
hammeramr [deleted]tigerleapgorge [deleted]cowarrior1 is the time complexity O(n^2) for this one?
almatsboom Amazing!
cellepo Thanks for helping to discover Morris' exists!
Here is my Java solution of essentially the same (passes all tests) with code comments. Main difference is that predecessor's right-child is "threaded" back to what it is truly a predecessor of (in this preorder problem case), which is cur.right (not just cur, which would be the case for INorder) - that allows some other differences (don't have to arrive at predecessor a 2nd time, therefore nor un-"threading" predecessor's right-child; no predecessor-finding when its not necessary [when cur has no right-child]), which all aggregate to make this slightly more efficient runtime (but not not complexity still O(n)), I believe.
public static void preOrder(Node root) { Node cur = root; while(cur != null){ System.out.print(cur.data + " "); if(cur.left != null & cur.right != null){ // Find in-order predecessor of cur // (that predecessor is also the last node to attempt visiting its right, // directly before attempting visiting cur's right) Node pred = cur.left; while(pred.right != null){ pred = pred.right; } // Thread pred.right to cur.right (to "remember" it without a stack) pred.right = cur.right; } if(cur.left != null){ // "Recur" on left cur = cur.left; } else { // "Recur" on right cur = cur.right; } } }
oreldm Same solution with java:
public static void preOrder(Node root) { if(root == null ) return ; Node pre; Node curr = root; while(curr!=null){ if(curr.left == null){ System.out.print(curr.data+" "); curr=curr.right; continue; } 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{ curr = curr.right; } } }
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.
P1xt1 Can we get JavaScript and Golang added?
feng12 I want Golang too!
leninlawrence111 Me too
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)
aramhmd in python 3 you can set the end to "" :
print(statement, end="")
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.
melvillej260 Dash board hacker rank is a website that has an ability to hack a software. They are offering jobs for everyone who has skills related to them. You can write my book review for me to complete your quality task easily. It also has a self statement blogs available. Join it for more.
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
kanak_kvian [deleted]
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
Sean83 The concept for Python3 is the same. The difference is just the way of using print function. (i.e. end parameter within the function)
Executive_Author How input can know which is left or right child
Sort 257 Discussions, By:
Please Login in order to post a comment