We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
publicstaticvoidpreOrder(Noderoot){Nodecur=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)Nodepred=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 leftcur=cur.left;}else{// "Recur" on rightcur=cur.right;}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tree: Preorder Traversal
You are viewing a single comment's thread. Return to all comments →
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.